java - Java でのパーティションの生成

Question

整数 (x と呼びましょう) が与えられ、配列の配列を生成する必要があります。ここで、各サブ配列は、指定された整数セットの 1 つである要素のリストであり、各サブ配列のすべての要素の合計です。 ×です。配列の配列には、この形式のすべての可能な個別のサブ配列を含める必要があります。

たとえば、x が 3 で、可能な要素のリストが {1, 2} の場合、{{1, 2}, {2, 1}} を生成しようとしています。

これを行うための最良の方法は何ですか（疑似コードまたはJavaで）？この 2D 配列は、このタイプのデータを格納するための最良の方法ですか? これ以上良いものは思いつきませんでしたが、そこには何かがあると思います。

Answer 1

ストレージには、おそらく HashSet の LinkedList が必要です。

LinkedList<HashSet<Integer>> l;

問題について: これは NP 完全な SubSet 問題であるため、既知の高速な方法はないと思います。私は最適化理論を使っていないので、入力のパワーセットを検索して、それらの合計のいずれかが出力と一致するかどうかを確認するのが最善の方法です。

Answer 2

「サブアレイ」のサイズがわからないので、Java のコレクションの 1 つを使用することをお勧めしますArrayList<E>。