Получить список комбинаций элементов списков

Предположим, что у меня есть 3 списка: ['q', 'w'], ['a', 's'], ['z', 'x']. Как получить список возможных комбинаций из этих списков? Поэтому я получаю список [['q', 'a', 'z'], ['q', 's', 'z']] и т.д. Я сделал метод для двоих, но не могу выбрать один для N списков:

static <e> ArrayList combine(ArrayList<e> one,ArrayList<e> two)
{
 ArrayList<arraylist<e>> combs=new ArrayList<arraylist<e>>();
 for(E e:one)
 {
 for(E e2:two)
 {
 ArrayList ps=new ArrayList();
 ps.add(e);
 ps.add(e2);
 combs.add(ps);
 }
 }
 return combs;
}
</arraylist<e></arraylist<e></e></e></e>

Я узнал, что это сделано Guava Sets.cartesianProduct.

4 ответа

Вам нужно N вложенных циклов, что и затрудняет работу.

Вы можете добиться этого, используя рекурсию.

static <e> ArrayList combine(ArrayList<e> soFar, ArrayList<e>... lists)
{
 // Rather than constantly making and remaking this list could just use one
 // and pass it around and add stuff to it. This works though.
 ArrayList<arraylist<e>> combs=new ArrayList<arraylist<e>>();
 // Loop through the first list looking for elements
 for(E e:lists[0])
 {
 // Create a new List to build this combination
 ArrayList<e> temp = new ArrayList<>(soFar);
 // Add this element to the combination
 temp.add(e);
 // If there are more lists recurse down
 if (lists.length > 1) {
 // Use recursion to add all combinations of the remaining lists
 combs.addAll(combine(temp, lists.subList(1)));
 } else {
 // There are no more lists so we are done, add temp to the combos
 combs.add(temp);
 }
 }
 return combs;
}
// Call this method to start things going, the other one should probably be private
static <e> ArrayList combine(ArrayList<e>... lists)
 return combine(new ArrayList<e>(), lists);
}
</e></e></e></e></arraylist<e></arraylist<e></e></e></e>


Для ленивых (используя Guava):

Set<list<string>> result = Sets.cartesianProduct(
 ImmutableSet.of("q", "w"),
 ImmutableSet.of("a", "s"),
 ImmutableSet.of("z", "x")
 );
System.out.println(result);
</list<string>

вывод:

[ [q, a, z], [q, a, x], [q, s, z], [q, s, x], [w, a, z], [w, a, x], [w, s, z], [w, s, x] ]


Возможно, вам захочется взглянуть на класс https://github.com/javagl/Combinatorics/blob/master/src/main/java/de/javagl/utils/math/combinatorics/MixedRangeCombinationIterable.java ( "отдельный" класс, просто скопируйте и вставьте в свой проект)

Пример использования:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Combinations
{
 public static void main(String[] args)
 {
 List<list<character>> lists = new ArrayList<list<character>>();
 lists.add(Arrays.asList('q','w'));
 lists.add(Arrays.asList('a','s'));
 lists.add(Arrays.asList('z','x'));
 MixedRangeCombinationIterable<character> iterable = 
 new MixedRangeCombinationIterable<character>(lists);
 for (List<character> element : iterable)
 {
 System.out.println(element);
 }
 }
}
</character></character></character></list<character></list<character>

Фактически вы вычисляете элементы http://en.wikipedia.org/wiki/Cartesian_product входных наборов


вверх вы можете создать внутренний класс с конструктором (Parameters...), поэтому вы можете поместить список этого класса, который обрабатывает все комбинации

licensed under cc by-sa 3.0 with attribution.