如何从多个列表中得到笛卡尔积？

Question

假设我有几个列表 ，我会将它们放入另一个列表或其他集合中，所以在调用列表 >.size() 之前，我不知道我有多少个列表

list1=[1,2]
list2=[3,4]
list3=[5,6]
....
listn=[2*n-1,2n];

list1*list2*list3

应该是：

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

Answer 1

您可以使用递归来实现它，递归的基本情况是当输入为空时返回空列表，否则处理剩余的元素。例如。

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class CartesianProduct {
    public static <T> List<List<T>> calculate(List<List<T>> input) {
        List<List<T>> res = new ArrayList<>();
        if (input.isEmpty()) { // if no more elements to process
            res.add(new ArrayList<>()); // then add empty list and return
            return res;
        } else {
            // we need to calculate the cartesian product
            // of input and store it in res variable
            process(input, res);
        }
        return res; // method completes , return result
    }

    private static <T> void process(List<List<T>> lists, List<List<T>> res) {
        //take first element of the list
        List<T> head = lists.get(0);
        //invoke calculate on remaining element, here is recursion
        List<List<T>> tail = calculate(lists.subList(1, lists.size()));

        for (T h : head) { // for each head
            for (List<T> t : tail) { //iterate over the tail
                List<T> tmp = new ArrayList<>(t.size());
                tmp.add(h); // add the head
                tmp.addAll(t); // and current tail element
                res.add(tmp);
            }
        }
    }

    public static void main(String[] args) {
        //we invoke the calculate method
        System.out.println(calculate(Arrays.asList(
                Arrays.asList(1, 2),
                Arrays.asList(3, 4),
                Arrays.asList(5, 6))));
    }
}

输出

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