それぞれの長さが不明なリストの量が不明な場合、考えられるすべての一意の組み合わせを含む単一のリストを生成する必要があります。たとえば、次のリストがあるとします。
X: [A, B, C]
Y: [W, X, Y, Z]
次に、12 の組み合わせを生成できるはずです。
[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]
3 つの要素の 3 番目のリストが追加された場合、36 の組み合わせが得られます。
Javaでこれを行う方法についてのアイデアはありますか?
(疑似コードでも構いません)
再帰が必要です：
すべてのリストが、リストのリストである にあるとしましょうlists。result必要な順列のリストになります。次のように実装できます。
void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
if (depth == lists.size()) {
result.add(current);
return;
}
for (int i = 0; i < lists.get(depth).size(); i++) {
generatePermutations(lists, result, depth + 1, current + lists.get(depth).get(i));
}
}
最終的な呼び出しは次のようになります。
generatePermutations(lists, result, 0, "");
リストの一般的なリストで機能するイテレータベースの回答を追加し、List<List<T>>Ruslan Ostafiichuk の回答からアイデアを拡張します。私が従ったアイデアは次のとおりです。
* List 1: [1 2]
* List 2: [4 5]
* List 3: [6 7]
*
* Take each element from list 1 and put each element
* in a separate list.
* combinations -> [ [1] [2] ]
*
* Set up something called newCombinations that will contains a list
* of list of integers
* Consider [1], then [2]
*
* Now, take the next list [4 5] and iterate over integers
* [1]
* add 4 -> [1 4]
* add to newCombinations -> [ [1 4] ]
* add 5 -> [1 5]
* add to newCombinations -> [ [1 4] [1 5] ]
*
* [2]
* add 4 -> [2 4]
* add to newCombinations -> [ [1 4] [1 5] [2 4] ]
* add 5 -> [2 5]
* add to newCombinations -> [ [1 4] [1 5] [2 4] [2 5] ]
*
* point combinations to newCombinations
* combinations now looks like -> [ [1 4] [1 5] [2 4] [2 5] ]
* Now, take the next list [6 7] and iterate over integers
* ....
* 6 will go into each of the lists
* [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] ]
* 7 will go into each of the lists
* [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] [1 4 7] [1 5 7] [2 4 7] [2 5 7]]
今コード。Set単純に重複を取り除くためにa を使用しました。に置き換えることができますList。すべてがシームレスに機能する必要があります。:)
public static <T> Set<List<T>> getCombinations(List<List<T>> lists) {
Set<List<T>> combinations = new HashSet<List<T>>();
Set<List<T>> newCombinations;
int index = 0;
// extract each of the integers in the first list
// and add each to ints as a new list
for (T i : lists.get(0)) {
List<T> newList = new ArrayList<T>();
newList.add(i);
combinations.add(newList);
}
index++;
while (index < lists.size()) {
List<T> nextList = lists.get(index);
newCombinations = new HashSet<List<T>>();
for (List<T> first : combinations) {
for (T second : nextList) {
List<T> newList = new ArrayList<T>();
newList.addAll(first);
newList.add(second);
newCombinations.add(newList);
}
}
combinations = newCombinations;
index++;
}
return combinations;
}
少しテストブロック..
public static void main(String[] args) {
List<Integer> l1 = Arrays.asList(1, 2, 3);
List<Integer> l2 = Arrays.asList(4, 5);
List<Integer> l3 = Arrays.asList(6, 7);
List<List<Integer>> lists = new ArrayList<List<Integer>>();
lists.add(l1);
lists.add(l2);
lists.add(l3);
Set<List<Integer>> combs = getCombinations(lists);
for (List<Integer> list : combs) {
System.out.println(list.toString());
}
}
実装する必要がある操作は、デカルト積と呼ばれます。詳細については、https://en.wikipedia.org/wiki/Cartesian_productを参照してください。
必要なことを正確に実行できるオープン ソース ライブラリを使用することをお勧めします: https://github.com/SurpSG/Kombi
使用方法の例があります: https://github.com/SurpSG/Kombi#usage-for-lists-1
注: このライブラリは、高性能を目的として設計されています。ここでバンクマークの結果を確認できます
このライブラリは、かなり優れたスループットと一定のメモリ使用量を提供します
ここで他の回答で提供されているネストされたループソリューションを使用して、2 つのリストを結合します。
リストが 2 つ以上ある場合は、