Gere todas as combinações de várias listas

Dada uma quantidade desconhecida de listas, cada uma com um tamanho desconhecido, preciso gerar uma lista única com todas as combinações únicas possíveis. Por exemplo, dadas as seguintes listas:

X: [A, B, C] Y: [W, X, Y, Z] 

Então eu deveria ser capaz de gerar 12 combinações:

 [AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ] 

Se uma terceira lista de 3 elementos fosse adicionada, eu teria 36 combinações e assim por diante.

Alguma idéia de como eu posso fazer isso em Java?
(pseudo código seria bom também)

Você precisa de recursion:

Digamos que todas as suas listas estejam em Lists , que é uma lista de listas. Deixe o resultado ser a lista de suas permutações necessárias: Faça assim

 void GeneratePermutations(List> Lists, List 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)); } } 

A última chamada será assim

 GeneratePermutations(Lists, Result, 0, EmptyString); 

Este tópico veio a calhar. Eu reescrevi a solução anterior totalmente em Java e mais amigável. Além disso, uso collections e genéricos para mais flexibilidade:

 /** * 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. * * 
    Example *
  • Input = { {a,b,c} , {1,2,3,4} }
  • *
  • 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} }
  • *
* * @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 Collection> permutations(List> collections) { if (collections == null || collections.isEmpty()) { return Collections.emptyList(); } else { Collection> res = Lists.newLinkedList(); permutationsImpl(collections, res, 0, new LinkedList()); return res; } } /** Recursive implementation for {@link #permutations(List, Collection)} */ private static void permutationsImpl(List> ori, Collection> res, int d, List 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 currentCollection = ori.get(d); for (T element : currentCollection) { List copy = Lists.newLinkedList(current); copy.add(element); permutationsImpl(ori, res, d + 1, copy); } }

Estou usando biblioteca de goiabas para criação de collections.

Sem combinações únicas de recursion:

  String sArray[] = new String []{"A", "A", "B", "C"}; //convert array to list List list1 = Arrays.asList(sArray); List list2 = Arrays.asList(sArray); List list3 = Arrays.asList(sArray); LinkedList> lists = new LinkedList>(); lists.add(list1); lists.add(list2); lists.add(list3); Set combinations = new TreeSet(); Set newCombinations; for (String s: lists.removeFirst()) combinations.add(s); while (!lists.isEmpty()) { List next = lists.removeFirst(); newCombinations = new TreeSet(); for (String s1: combinations) for (String s2 : next) newCombinations.add(s1 + s2); combinations = newCombinations; } for (String s: combinations) System.out.print(s+" "); 

Adicionando uma resposta baseada em iterador para trabalhar para uma lista genérica de listas List> , estendendo a ideia da resposta de Ruslan Ostafiichuk. A ideia que eu segui foi:

  * 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]] 

Agora o código. Eu usei um Set simplesmente para me livrar de quaisquer duplicatas. Pode ser substituído por uma List . Tudo deve funcionar sem problemas. 🙂

 public static  Set> getCombinations(List> lists) { Set> combinations = new HashSet>(); Set> 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 newList = new ArrayList(); newList.add(i); combinations.add(newList); } index++; while(index < lists.size()) { List nextList = lists.get(index); newCombinations = new HashSet>(); for(List first: combinations) { for(T second: nextList) { List newList = new ArrayList(); newList.addAll(first); newList.add(second); newCombinations.add(newList); } } combinations = newCombinations; index++; } return combinations; } 

Um pequeno bloco de teste ..

 public static void main(String[] args) { List l1 = Arrays.asList(1,2,3); List l2 = Arrays.asList(4,5); List l3 = Arrays.asList(6,7); List> lists = new ArrayList>(); lists.add(l1); lists.add(l2); lists.add(l3); Set> combs = getCombinations(lists); for(List list : combs) { System.out.println(list.toString()); } } 

Esta operação é chamada de produto cartesiano . Guava fornece uma function de utilidade para isso: Lists.cartesianProduct

Use a solução de loop nested fornecida por algumas outras respostas aqui para combinar duas listas.

Quando você tem mais de duas listas,

  1. Combine os dois primeiros em uma nova lista.
  2. Combine a lista resultante com a próxima lista de input.
  3. Repetir.
  • Sem recursion
  • Está encomendado
  • Possível obter uma combinação específica por seu índice (sem construir todas as outras permutações):

Método de class e main() no final:

 public class TwoDimensionalCounter { private final List> elements; public TwoDimensionalCounter(List> elements) { this.elements = Collections.unmodifiableList(elements); } public List get(int index) { List result = new ArrayList<>(); for(int i = elements.size() - 1; i >= 0; i--) { List 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 next: elements) result *= next.size(); return result; } public static void main(String[] args) { TwoDimensionalCounter 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)); } } 

tarde para a festa, como de costume, mas aqui está um exemplo bem explicado usando matrizes, pode ser facilmente alterado para listas. Eu precisava de todas as combinações únicas de vários arrays para o meu caso de uso em ordem lexicográfica.

Eu postei isso como nenhuma das respostas aqui dá um algoritmo claro, e eu não suporto recursion. Não estamos no stackoverflow afinal?

 String[][] combinations = new String[][] { new String[] { "0", "1" }, new String[] { "0", "1" }, new String[] { "0", "1" }, new String[] { "0", "1" } }; int[] indices = new int[combinations.length]; int currentIndex = indices.length - 1; outerProcess: while (true) { for (int i = 0; i < combinations.length; i++) { System.out.print(combinations[i][indices[i]] + ", "); } System.out.println(); while (true) { // Increase current index indices[currentIndex]++; // If index too big, set itself and everything right of it to 0 and move left if (indices[currentIndex] >= combinations[currentIndex].length) { for (int j = currentIndex; j < indices.length; j++) { indices[j] = 0; } currentIndex--; } else { // If index is allowed, move as far right as possible and process next // combination while (currentIndex < indices.length - 1) { currentIndex++; } break; } // If we cannot move left anymore, we're finished if (currentIndex == -1) { break outerProcess; } } } 

A saída;

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

A operação que você precisa implementar chamado Produto Cartesiano . Para mais detalhes, consulte https://en.wikipedia.org/wiki/Cartesian_product

Eu recomendo usar minha biblioteca de código aberto que pode fazer exatamente o que você precisa: https://github.com/SurpSG/Kombi

Há um exemplo de como usá-lo: https://github.com/SurpSG/Kombi#usage-for-lists-1

Nota : A biblioteca foi projetada para propósitos de alto desempenho . Você pode observar os resultados banchmarks aqui

A biblioteca oferece uma boa taxa de transferência e uso constante de memory

Aqui está uma amostra usando máscara de bits. Nenhuma recursion e várias listas

 static List allComboMatch(List numbers, int target) { int sz = (int)Math.pow(2, numbers.size()); for (int i = 1; i < sz; i++) { int sum = 0; ArrayList result = new ArrayList(); for (int j = 0; j < numbers.size(); j++) { int x = (i >> j) & 1; if (x == 1) { sum += numbers.get(j); result.add(j); } } if (sum == target) { return result; } } return null; }