整数の等しくないパーティションを見つける効率的な方法

Question

私は整数の合計パーティションを持っており、すべての値が等しくないパーティションだけを必要とします。例えば、3のパーティションは{1,1,1,1}、{2,2}、{3,1}、{1,1,2}、{4}です。したがって、必要な不等分割は{3,1}と{4}です。なぜならそれらは等しい要素を含んでいないからです。 私はすべてのパーティションを見つけるために使用したコードを以下に示します。パーティションをフィルタリングして目的の結果を得ることができますが、すべてのパーティションを見つけることなく、同等の用語を持たないすべてのパーティションを見つける効率的な方法が必要です。私はネットとstackoverflowを検索しているが、私が直面している問題はまったく述べていない。すべてのアイデアは高く評価されます。ありがとう。

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 
} 

Answer 1

このように、指定したコンポーネントが1回だけ表示されるパーティションは欲しいですか？再帰は単純です。

Nのパーティションについて解決する問題にそれを減らします。その結果、セット内のどの要素もいくつかの値a（最初はNになります）より大きくなりません。これで、どちらかがパーティションに表示されるかどうか。これに応じて、（N-a）のパーティションがa-1よりも大きくならないように、またNのパーティションではa-1より大きいメンバーがないように再帰的に解きます。

いずれの場合も、再帰はよくポーズされ、問題を解決することができなくなったときに終了するので、a *（a + 1）/ 2 < Nのときに終了します。もちろん、* a + 1）/ 2 = Nの場合、ソリューションが一意であるため、再帰をすばやく終了することもできます。