生成多個列表中的所有組合給定未知數量的列表，每個列表具有未知長度，我需要生成具有所有可能的唯一組合的單個列表。例如，給出以下列表：X: [A, B, C] Y: [W, X, Y, Z]然后我應該能夠生成12種組合：[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]如果添加了3個元素的第三個列表，我將有36個組合，依此類推。關于如何用Java做到這一點的任何想法？（偽代碼也可以）
3 回答
aluckdog
TA貢獻1847條經驗 獲得超7個贊
你需要遞歸：
假設您的所有列表都在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, "");
PIPIONE
TA貢獻1829條經驗 獲得超9個贊
這個話題派上了用場。我用Java完全重寫了以前的解決方案，更加用戶友好。此外，我使用集合和泛型來獲得更大的靈活性：
/**
* Combines several collections of elements and create permutations of all of them, taking one element from each
* collection, and keeping the same order in resultant lists as the one in original list of collections.
*
* <ul>Example
* <li>Input = { {a,b,c} , {1,2,3,4} }</li>
* <li>Output = { {a,1} , {a,2} , {a,3} , {a,4} , {b,1} , {b,2} , {b,3} , {b,4} , {c,1} , {c,2} , {c,3} , {c,4} }</li>
* </ul>
*
* @param collections Original list of collections which elements have to be combined.
* @return Resultant collection of lists with all permutations of original list.
*/public static <T> Collection<List<T>> permutations(List<Collection<T>> collections) {
if (collections == null || collections.isEmpty()) {
return Collections.emptyList();
} else {
Collection<List<T>> res = Lists.newLinkedList();
permutationsImpl(collections, res, 0, new LinkedList<T>());
return res;
}}/** Recursive implementation for {@link #permutations(List, Collection)} */private static <T> void permutationsImpl(List<Collection<T>> ori, Collection<List<T>> res, int d, List<T> current) {
// if depth equals number of original collections, final reached, add and return
if (d == ori.size()) {
res.add(current);
return;
}
// iterate from current collection and copy 'current' element N times, one for each element
Collection<T> currentCollection = ori.get(d);
for (T element : currentCollection) {
List<T> copy = Lists.newLinkedList(current);
copy.add(element);
permutationsImpl(ori, res, d + 1, copy);
}}我正在使用guava庫來創建集合。
添加回答
舉報
0/150
提交
取消