これを行うアルゴリズムが必要です：
順序を気にせずに、指定された合計を「バケット」に分割する一意の方法をすべて見つけます
私がいたことを願っていますクリア自分を表現する上で適度に首尾一貫している。
合計 5 バケットと 3 バケットの場合、アルゴリズムが返すものは次のとおりです。
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1] [2, 2, 1]
この質問がだまされている可能性がある場合は申し訳ありませんが、この種の問題が何と呼ばれているのか正確にはわかりません。それでも、考えられるすべての表現を使用して Google と SO で検索しましたが、すべてがユニークな方法ではなく、最も均等な方法で配布するという結果しか見つかりませんでした。
アルゴリズムについて 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)) になります。
動的計画法がないのはなぜですか?
これらすべての可能性の数を見つけたくないので、同じポイントに再び到達したとしても、とにかくすべての数値を出力する必要があるため、複雑さは同じままです.
少しでも参考になれば幸いです 質問等お気軽にどうぞ
この答えに依存する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]]
まったく異なる方法ですが、効率や最適化を気にしない場合は、常に古い「バケットフリー」パーティションアルゴリズムを使用できます。次に、回答のゼロの数を確認することで、検索をフィルタリングできます。
たとえば[1,1,1,1,1]、バケットが3つを超えるため無視されますが、[2,2,1,0,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;
}
バケットが 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)+"]");
}
}
これは整数分割と呼ばれます。
Fast Integer Partition Algorithmsは、整数分割を実行するための最速のアルゴリズムをすべて説明した包括的な論文です。