1

特定の方法でセットのパーティションを生成したいと思います。これらのパーティションを生成するプロセスで、サイズが N でないすべてのパーティションを除外する必要があります。一般的な解決策は、「セットのすべての「一意の」サブセットを生成する(パワーセットではない)」です。

S次のサブセットを含むセットの場合:

[a,b,c]
[a,b]
[c]
[d,e,f]
[d,f]
[e]

および次の「一意の」要素:

a, b, c, d, e, f

引数で実行された関数/メソッドの結果は次のN = 2ようになります。

[[a,b,c], [d,e,f]]

次のパーティションは、関数/メソッドによって除外する必要があります。

[[a,b,c], [d,f], [e]]
[[a,b], [c], [d,e,f]]
[[a,b], [c], [d,f], [e]]

基礎となるデータ構造は重要ではなく、配列、セットなどの可能性があります。


理由: すべてのパーティションを生成する関数/メソッドはかなり計算量が多いため、すべてのパーティションの完全なセットを取得する前に、いくつかのパーティションを除外する必要があります。


「セットのパーティションの生成」によると、可能なパーティションの数は非常に多くなる可能性があります: 23 要素の場合、44152005855084346 です。私のデータは開始セットで 50 ~ 300 要素なので、どこかに保存する前に、N と等しくないサイズのパーティションを確実に除外する必要があります。

4

1 に答える 1

0

partitionsFrederick Cheung から提供されたリンクを取得したら、次の操作を行います。

partitions.select{|partition| partition.length == 2}
于 2011-12-27T16:11:51.920 に答える