如何从多个列表中获取笛卡尔积? [英] How to get Cartesian product from multiple lists?

问题描述

说我有几个List，我会把它们放到另一个列表或其他集合中，所以我不知道有多少list直到我调用 List>.size()

Say I have several List<T>s, I will put them into another list or other collections, so I don't know how many list<T> I have until I call List<List<T>>.size()

下面以List为例:

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

如何将list1*list2*list3*...listn的结果作为笛卡尔积?

How can I get the result of list1*list2*list3*...listn as a Cartesian product?

例如:

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]

推荐答案

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

You can use recursion to achieve it, your base case of recursion is when input is empty then return empty list, else process the remaining elements. E.g.

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]]

这篇关于如何从多个列表中获取笛卡尔积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！