如何迭代List<List<T>>的所有组合

Question

我有一个List<List<T>>，两个列表维度的长度都是不同的。

Using recursion I can calculate all the combinations

几个例子List<List<T>>及其组合

[
 [1],
 [2, 3],
 [4, 5, 6]
] 
// [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6]

[ 
 [0, 4],
 [3, 4, 1, 2]
]
// [0, 3], [0, 4], [0, 1], [0, 2], [4, 3], [4, 4], [4, 1], [4, 2]

[ 
 ["A", "B", "B"],
 ["C"]
]
// ["A", "C"], ["B", "C"], ["B, "C"]

组合的数量可以快速增长，使用递归将成为内存和性能问题。

在计算组合时，我如何实现迭代器来迭代它们？

做一些阅读，我可能会使用一个阶乘或组合数字系统，但我不知道如何应用它在这种情况下。

Answer 1

编辑此答案以适用于List<List<T>>。tobias的答案使用一个iterator来迭代列表的索引，从而得到下一个组合。这做了一些类似的事情，没有基于迭代器的方法。我遵循的想法是：

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

}