生成多个列表中的所有组合

Question

给定未知数量的列表,每个列表具有未知长度,我需要生成具有所有可能的唯一组合的单个列表.例如,给出以下列表:

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做到这一点的任何想法？
(伪代码也可以)

Answer 1

你需要递归:

假设您的所有列表都在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, "");

Answer 2

这个话题派上了用场.我用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库来创建集合.

Answer 3

此操作称为笛卡尔积.Guava提供了一个实用功能:Lists.cartesianProduct

Answer 4

没有递归的独特组合:

    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+" ");    

Answer 5

添加基于迭代器的答案来处理列表的通用列表,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.一切都应该无缝地工作.:)

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());
    }

}

Answer 6

您需要实现的操作称为Cartesian Product。有关更多详细信息，请参阅https://en.wikipedia.org/wiki/Cartesian_product

我建议使用我的开源库，它可以完全满足您的需求：https : //github.com/SurpSG/Kombi

有如何使用它的示例：https : //github.com/SurpSG/Kombi#usage-for-lists-1

注意：该库是为高性能目的而设计的。您可以在此处观察基准结果

该库为您提供了非常好的吞吐量和恒定的内存使用量