0

整数のパーティションの合計があり、すべての値が等しくないパーティションのみが必要です。例-3のパーティションは、{1,1,1,1}、{2,2}、{3,1}、{1,1,2}、および{4}です。したがって、必要な等しくないパーティションは、等しい要素が含まれていないため、{3,1}と{4}です。すべてのパーティションを見つけるために使用したコードを以下に示します。パーティションをフィルタリングして目的の結果を得ることができますが、すべてのパーティションを検索せずに、等しい用語が含まれていないすべてのパーティションを効率的に検索する方法が必要です。私はネットとスタックオーバーフローを検索しましたが、私が直面している問題を正確に述べているものは何もありません。すべてのアイデアは高く評価されています。ありがとう。

function total_partitions_of_a_number($n) {# base case of recursion: zero is the sum of the empty list
if(!$n) return array(array()); # return empty array

# modify partitions of n-1 to form partitions of n
foreach(total_partitions_of_a_number($n-1) as $p) { # recursive call
 $a[] = array_merge(array(1), $p); # "yield" array [1, p...]
 if($p && (count($p) < 2 || $p[1] > $p[0])) { # p not empty, and length < 2 or p[1] > p[0]
   ++$p[0]; # increment first item of p
   $a[] = $p; # "yield" p
 }
}
return $a; # return all "yielded" values at once
}
4

1 に答える 1

2

では、特定のコンポーネントが 1 回しか表示されないパーティションのみが必要ですか? 再帰は単純です。

セット内のどの要素も値 a よりも大きくならないように、N の分割を解く問題にそれを減らします (a は最初は N になります)。これに応じて、a-1 より大きい要素がないような (Na) の分割と、a-1 より大きい要素がないように N の分割の両方を再帰的に解きます。

いずれの場合も、再帰は適切に設定されており、問題を解決できなくなった時点で終了します。つまり、a*(a+1)/2 < N の場合です。もちろん、a*(a+1) の場合は、 /2 = N、ソリューションが一意であるため、再帰をすばやく終了することもできます。

于 2012-04-07T12:28:10.593 に答える