java - 3 个集合的笛卡尔积

Question

我需要从 3 个列表中计算笛卡尔积。 这是代码。

XList<T> combine() {
    XList<T> returnList = new XList<>();

    List<T> list = new ArrayList(this.coll);
    List<T> a = (List<T>) list.get(0);
    List<T> b = (List<T>) list.get(1);
    List<T> c = (List<T>) list.get(2);

    //working
    //List<XList<T>> ll2 = a.stream()
    //        .flatMap(ai -> b.stream()
    //                .map(bi -> new XList<>(Arrays.asList(ai, bi))))
    //        .collect(Collectors.toList());

    // not working
    List<XList<T>> ll3 = a.stream()
            .flatMap(ai -> b.stream()
                    .flatMap(bi -> c.stream()
                            .map(ci -> new XList<>(Arrays.asList(ai, bi, ci)))))
            .collect(Collectors.toList());

    returnList.coll = (Collection<T>) ll3;

    return returnList;
}

当我尝试从列表 a 和 b 中执行笛卡尔积时，它正在工作，但如果我想使用 a、b 和 c 执行此操作，它会重新调整一个空列表。有什么问题吗？ 谢谢您的回复。

Answer 1

您可以使用三个嵌套的for 循环生成多个集合的笛卡尔积。将传入集合中的数据依次添加到中间结果中并获得最终结果。从原理上讲，它看起来像这样:

res0: [[]]
col1: [1,2,3]
----
res1: [[1],[2],[3]]
col2: [4,5,6]
----
res2: [[1,4],[1,5],[1,6],[2,4],[2,5]...,[3,6]]
col3: [7,8,9]
----
res3: [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8]...,[3,6,9]]

Try it online!

/**
 * @param cols an arbitrary number of collections
 * @param <T>  the type of the elements
 * @return the Cartesian product
 */
@SafeVarargs
public static <T> List<List<T>> cartesianProduct(Collection<T>... cols) {
    // check if incoming data is not null
    if (cols == null) return Collections.emptyList();
    // Cartesian product, intermediate result
    List<List<T>> cp = Collections.singletonList(Collections.emptyList());
    // iterate through the incoming collections
    for (Collection<T> col : cols) {
        // non-null and non-empty collections
        if (col == null || col.size() == 0) continue;
        // intermediate result for next iteration
        List<List<T>> next = new ArrayList<>();
        // rows of current intermediate result
        for (List<T> row : cp) {
            // elements of current list
            for (T el : col) {
                // new row for next intermediate result
                List<T> nRow = new ArrayList<>(row);
                nRow.add(el);
                next.add(nRow);
            }
        }
        // pass to next iteration
        cp = next;
    }
    // Cartesian product, final result
    return cp;
}

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(1, 2, 3);
    List<Integer> list2 = Arrays.asList(4, 5, 6);
    List<Integer> list3 = Arrays.asList(7, 8, 9);

    List<List<Integer>> cp = cartesianProduct(list1, list2, list3);
    // column-wise output
    int rows = 9;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cp.size(); j++)
            System.out.print(j % rows == i ? cp.get(j) + " " : "");
        System.out.println();
    }
}

输出:

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

<小时/>

^{另请参阅:How to get Cartesian product from multiple lists?}