2

問題

これを行うアルゴリズムが必要です：

順序を気にせずに、指定された合計を「バケット」に分割する一意の方法をすべて見つけます

私がいたことを願っていますクリア自分を表現する上で適度に首尾一貫している。

例

合計 5 バケットと 3 バケットの場合、アルゴリズムが返すものは次のとおりです。

[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1] [2, 2, 1]

免責事項

この質問がだまされている可能性がある場合は申し訳ありませんが、この種の問題が何と呼ばれているのか正確にはわかりません。それでも、考えられるすべての表現を使用して Google と SO で検索しましたが、すべてがユニークな方法ではなく、最も均等な方法で配布するという結果しか見つかりませんでした。

4

6 に答える 6

2

アルゴリズムについて 5 ページのエッセイを書くよりも、数行コーディングする方が少し簡単です。考えられる最も単純なバージョンは次のとおりです。

vector<int> ans;

void solve(int amount, int buckets, int max){
  if(amount <= 0) { printAnswer(); return;}
  if(amount > buckets * max) return; // we wont be able to fulfill this request anymore

  for(int i = max; i >= 1; i--){
    ans.push_back(i);
    solve(amount-i, buckets-1, i);
    ans.pop_back();
  } 
}

void printAnswer(){
  for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
  for(int i = 0; i < all_my_buckets - ans.size(); i++) printf("0 ");
  printf("\n");
}

また、選択肢を積み重ねるポイントまで改善する価値もあります。solve( amount-k*i, buckets-k, i-1)そのため、深すぎる再発を作成することはありません。(私が知る限り、スタックのサイズは O(sqrt(n)) になります。

動的計画法がないのはなぜですか?

これらすべての可能性の数を見つけたくないので、同じポイントに再び到達したとしても、とにかくすべての数値を出力する必要があるため、複雑さは同じままです.

少しでも参考になれば幸いです 質問等お気軽にどうぞ

于 2013-03-13T15:17:46.967 に答える
1

この答えに依存するHaskellの何かがあります：

import Data.List (nub, sort)

parts 0 = []
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)]

partitions n buckets = 
  let p = filter (\x -> length x <= buckets) $ parts n 
  in map (\x -> if length x == buckets then x else addZeros x) p  
    where addZeros xs = xs ++ replicate (buckets - length xs) 0


OUTPUT:
*Main> partitions 5 3
[[5,0,0],[1,4,0],[1,1,3],[1,2,2],[2,3,0]]
于 2013-03-13T15:57:16.270 に答える
0

まったく異なる方法ですが、効率や最適化を気にしない場合は、常に古い「バケットフリー」パーティションアルゴリズムを使用できます。次に、回答のゼロの数を確認することで、検索をフィルタリングできます。

たとえば[1,1,1,1,1]、バケットが3つを超えるため無視されますが、[2,2,1,0,0]合格します。

于 2013-03-13T14:59:06.843 に答える
0

他のアプローチと一緒にここに私のアプローチを追加するだけです。これは Python で書かれているため、実際には疑似コードに似ています。

私の最初のアプローチはうまくいきましたが、恐ろしく非効率的でした:

def intPart(buckets, balls):
    return uniqify(_intPart(buckets, balls))

def _intPart(buckets, balls):
    solutions = []

    # base case
    if buckets == 1:
        return [[balls]]

    # recursive strategy
    for i in range(balls + 1):
        for sol in _intPart(buckets - 1, balls - i):
            cur = [i]
            cur.extend(sol)
            solutions.append(cur)

    return solutions

def uniqify(seq):
    seen = set()
    sort = [list(reversed(sorted(elem))) for elem in seq]
    return [elem for elem in sort if str(elem) not in seen and not seen.add(str(elem))]

これが私の再加工されたソリューションです。max_ 変数を使用して前のバケット内のボールを追跡することにより、それを「一意化」する必要が完全に回避されます。これにより、リストがソートされ、重複が防止されます。

def intPart(buckets, balls, max_ = None):
    # init vars
    sols = []
    if max_ is None:
        max_ = balls
    min_ = max(0, balls - max_)

    # assert stuff
    assert buckets >= 1
    assert balls >= 0

    # base cases
    if (buckets == 1):
        if balls <= max_:
            sols.append([balls])
    elif balls == 0:
        sol = [0] * buckets
        sols.append(sol)

    # recursive strategy
    else:
        for there in range(min_, balls + 1):
            here = balls - there
            ways = intPart(buckets - 1, there, here)
            for way in ways:
                sol = [here]
                sol.extend(way)
                sols.append(sol)

    return sols

包括性のために 、Perl で書かれたMJDから盗まれた別の回答を次に示します。

#!/usr/bin/perl

sub part {
  my ($n, $b, $min) = @_;
  $min = 0 unless defined $min;

  # base case
  if ($b == 0) {
    if ($n == 0) { return ([]) }
    else         { return ()   }
  }

  my @partitions;
  for my $first ($min .. $n) {
    my @sub_partitions = part($n - $first, $b-1, $first);
    for my $sp (@sub_partitions) {
      push @partitions, [$first, @$sp];
    }
  }
  return @partitions;
}
于 2013-03-14T13:33:18.833 に答える
0

バケットが 3 つしかない場合、これが最も単純なコードになります。 

for(int i=0;i<=5;i++){
        for(int j=0;j<=5-i&&j<=i;j++){
            if(5-i-j<=i && 5-i-j<=j)
                System.out.println("["+i+","+j+","+(5-i-j)+"]");
        }
}
于 2013-03-13T15:18:41.423 に答える
0

これは整数分割と呼ばれます。

Fast Integer Partition Algorithmsは、整数分割を実行するための最速のアルゴリズムをすべて説明した包括的な論文です。

于 2013-03-13T15:10:32.960 に答える