java - 从java中的列表>中查找所有排列(笛卡尔积)

Question

如果我有 n 个列表:

List<int> list1 = new List<int>
List<int> list2 = new List<int>
...
List<int> listn = new List<int>

它们每个都包含不同数量的元素，例如

list1.add(1)
list1.add(2)
list2.add(3)
list2.add(4)
list2.add(5)
list3.add(6)
...
listn.add(100000)
listn.add(100001)

和一个列表列表

List<List<int>> biglist = new ArrayList<List<int>>
biglist.add(list1)
biglist.add(list2)
...
biglist.add(listn)

那么如何从包含元素的biglist生成permuationList，假设listn有m个元素:

[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(1)]
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(2)]
...
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(m)]
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(2), biglist.get(n).get(1)]
....

谢谢!

Answer 1

您可以使用递归来实现此目的，将第一个列表与尾部列表(列表的列表)合并。

public class Permutation   {
    public static List<List<Integer>> calculate(List<List<Integer>> input) {
        List<List<Integer>> result= new ArrayList<List<Integer>>();//

        if (input.isEmpty()) {  // If input is an empty list
            result.add(new ArrayList<Integer>());// then add empty list to the resultand return
            return result;
        } else {//here we have a non-empty list to process
            List<Integer> head = input.get(0);//get the first list as a head
            List<List<Integer>> tail= calculate(input.subList(1, input.size()));//recursion to calculate a tail list to calculate a tail list
            for (Integer h : head) {//we merge every head element with every tail list
                for (List<Integer> t : tail) {
                    List<Integer> resultElement= new ArrayList<Integer>();//here is a new element of our result list
                    resultElement.add(h);//firstly, add the head element to this tmp list
                    resultElement.addAll(t);//add all the element from the tail list
                    result.add(resultElement);
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        List<List<Integer>> bigList=Arrays.asList(Arrays.asList(1,2),Arrays.asList(3,4),Arrays.asList(5,6));
        System.out.println(calculate(bigList));
    }
}

输出:

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