6

順序が重要なべき集合のすべての順列を計算するメソッドを作成しようとしています。これらは「アレンジメント」と呼ばれていると思います。これが意味するのは：

{a} -> {{a}, {}}
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}}
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}

私の印象では、集合Sが与えられた場合、Sのべき集合のすべてのサブセットのすべての順列を生成する必要があります。したがって、最初にべき集合を生成し、次に順列関数を各集合にマップします。

問題は、これが非常に複雑であるということです-k = 0..nのO（∑n！/ k！）のようなものです。

この種のことを非常に効率的に行う既存のアルゴリズムがあるかどうか疑問に思います（おそらく並列実装）。または、並列べき集合アルゴリズムが存在し、並列置換アルゴリズムが存在する場合でも、2つを組み合わせることができます。

考え？

4

2 に答える 2

1

googleが提供するguavaライブラリには、コレクションを並べ替えるためのさまざまなメソッドが含まれています。

ここでクラスcom.google.common.collect.Collections2のjavadocを参照してください。

于 2012-06-19T15:31:03.943 に答える
0

これを行うには、最初に1-nスロットの組み合わせを生成します。ここで、nはべき集合の要素の数です。たとえば、3つの要素がある場合、次のようになります。

C（3、3）= 1つの組み合わせ（abc）
C（3、2）= 3つの組み合わせ（ab）（ac）（bc）
C（3、1）= 3つの組み合わせ（a）（b）（c）

ここで、各組み合わせの順列を生成します。

順列と組み合わせを計算するためのよく知られたアルゴリズムがあります。たとえば、Knuthの「TheArt of Computer Programming」、第4A巻、セクション7.2.1.2および7.2.1.3は、関連するアルゴリズムを構築する方法を正確に説明しています。

于 2012-09-20T22:34:14.737 に答える