从多个列表中生成所有组合
给定未知数量的列表，每个列表的长度都不知道，我需要用所有可能的独特组合来生成一个单独的列表。 例如，给出以下列表：
X: [A, B, C] Y: [W, X, Y, Z] 那么我应该能够产生12种组合：
[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]
如果添加了第三个元素的列表，我会有36个组合，依此类推。
任何想法，我怎么能在Java中做到这一点？
（伪代码也可以）
你需要recursion：
假设所有的列表都在Lists ，这是列表的列表。 让结果成为您所需的排列列表：像这样做
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, EmptyString);
这个话题派上用场。 我已经用Java完全重写了以前的解决scheme，并且更加友好。 此外，我使用集合和generics更灵活：
/** * 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); } }
我正在使用番石榴库进行collections创作。
添加一个基于迭代器的答案来为通用列表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来摆脱任何重复。 可以用List来replace。 一切都应该无缝工作。 🙂
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; }
一个小testing块
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()); } }
没有recursion独特的组合：
String sArray[] = new String []{"A", "A", "B", "C"}; //convert array to list List<String> list1 = Arrays.asList(sArray); List<String> list2 = Arrays.asList(sArray); List<String> list3 = Arrays.asList(sArray); LinkedList<List <String>> lists = new LinkedList<List <String>>(); lists.add(list1); lists.add(list2); lists.add(list3); Set<String> combinations = new TreeSet<String>(); Set<String> newCombinations; for (String s: lists.removeFirst()) combinations.add(s); while (!lists.isEmpty()) { List<String> next = lists.removeFirst(); newCombinations = new TreeSet<String>(); for (String s1: combinations) for (String s2 : next) newCombinations.add(s1 + s2); combinations = newCombinations; } for (String s: combinations) System.out.print(s+" ");
使用这里提供的其他答案提供的嵌套循环解决scheme来组合两个列表。
当你有两个以上的列表时，
- 将前两个合并成一个新的列表。
- 将结果列表与下一个input列表组合。
- 重复。
- 没有recursion
- 被命令
- 可以通过其索引获得特定的组合（无需构build所有其他排列）：
类和main()方法到底：
public class TwoDimensionalCounter<T> { private final List<List<T>> elements; public TwoDimensionalCounter(List<List<T>> elements) { this.elements = Collections.unmodifiableList(elements); } public List<T> get(int index) { List<T> result = new ArrayList<>(); for(int i = elements.size() - 1; i >= 0; i--) { List<T> counter = elements.get(i); int counterSize = counter.size(); result.add(counter.get(index % counterSize)); index /= counterSize; } return result;//Collections.reverse() if you need the original order } public int size() { int result = 1; for(List<T> next: elements) result *= next.size(); return result; } public static void main(String[] args) { TwoDimensionalCounter<Integer> counter = new TwoDimensionalCounter<>( Arrays.asList( Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3) )); for(int i = 0; i < counter.size(); i++) System.out.println(counter.get(i)); } }
