1

のような文字列の arrayList があるとします[a, b, c, d, ....]。このリストから特定の文字列を含むすべての可能なパワーサブセットを含む結果を得るにはどうすればよいかというサンプルコードを手伝ってもらえますか?

a例:例のリストを含むすべての電力サブセットを取得したい場合、出力は次のようになります。

[a,b], [a,c], [a,d], [a,b,c], [a,b,d], [a,c,d] without the empty and single subset([a])

同様に、必要な場合b、出力は次のようになります。

[b,a], [b,c], [b,d], [b,a,c], [b,a,d], [b,c,d] without the empty and single subset([b])

例のリストの項目はすべて文字列であるため、サブセットが豊富すぎるとメモリの問題になる可能性があります。一度に 1 つの文字列に対して、このサブセットをメモリに保持する必要があるためです。では、このシナリオの最適化されたソリューションについても助けが必要ですか?

Java のヘルプが必要です。Javaはあまり得意ではないので、間違っていたらご容赦ください。

ありがとう！

4

1 に答える 1

2

文字列の最初の配列リストに 30 個以下の項目がある場合は、set メソッド powerSet を使用できます (http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html# powerSet%28java.util.Set%29 - ありがとう、ヨッヘン)。ドキュメントでは、そのメソッドによって返されるセットのセットのメモリ使用量は O(n) のみであると主張しています。次に、「A」を含み、サイズが 2 以上のセットのみを考慮する if 条件を使用して、それを繰り返すことができます。

最初に上記または同様の簡単な解決策を試して、メモリの問題が発生するかどうかを確認することをお勧めします。

メモリの問題が発生した場合は、メモリに保持する文字列のコピーの数を最小限に抑えることで最適化を試みることができます。たとえば、bytes、short、または int のリスト (arraylist の長さに応じて) を使用できます。ここで、それぞれは文字列の arraylist へのインデックスです。

ただし、メモリ使用量を削減する最終的な方法は、一度に 1 つのサブセットのみをメモリに保持することです (可能な場合)。つまり、(A, B) を生成し、処理し、破棄してから、(A, C) を生成し、処理し、破棄します。

于 2012-06-21T18:52:19.480 に答える