如何在Java中通过任意数字组创建笛卡尔积？

Question

假设我有两组数字:

{1, 2, 3},
{4, 5}

我想创建一个输出以下6种组合的算法(在Java中):

1,4
1,5
2,4
2,5
3,4
3,5

每组中可以有任意数量的组和任意数量的成员.因此在上面的例子中,有2组,第一组有3个成员,第二组有2个成员.另一个例子如下(3组,第一组3名成员,第2组和第3组2名成员):

{1, 2, 3},
{4, 5},
{6, 7}

这将产生以下12种组合:

1,4,6
1,4,7
1,5,6
1,5,7

2,4,6
2,4,7
2,5,6
2,5,7

3,4,6
3,4,7
3,5,6
3,5,7

我怎么能用Java做到这一点？我正在尝试使用递归,我已经看了一个类似的问题,但我仍然很短.谢谢您的帮助!(PS这不是作业作业)

Answer 1

有点无聊,决定试一试.应该正是您所需要的:

public static void main(String args[]) {

    ArrayList<int[]> input = new ArrayList<int[]>();
    input.add(new int[] { 1, 2, 3 });
    input.add(new int[] { 4, 5 });
    input.add(new int[] { 6, 7 });

    combine(input, new int[input.size()], 0);
}

private static void combine(ArrayList<int[]> input, int[] current, int k) {

    if(k == input.size()) {
        for(int i = 0; i < k; i++) {
            System.out.print(current[i] + " ");
        }
        System.out.println();
    } else {            
        for(int j = 0; j < input.get(k).length; j++) {
            current[k] = input.get(k)[j];
            combine(input, current, k + 1);
        }       
    }
}

Answer 2

如果你可以使用图书馆,番石榴的 Sets.cartesianProduct(List<Set<E>>)不正是你要寻找的.(披露:我向番石榴捐款.)

Answer 3

一种可能的方法（不一定是最有效的方法）可能是采用分而治之的方法。找到两组的所有排列是相对简单的（最愚蠢的方法只是嵌套在循环中）。假设您编写了一个名为的函数permute，该函数permute(A,B)在A（例如{（1），（2），（3）}）和B（例如{（4），（5）}）是一组数字的情况下返回了全部A和B的排列作为单个组（例如{（1,4），（1,5），（2,4），（2,5），（3,4），（3,5）}） 。

因此，当您有N个群组而不是2个群组时，最简单的方法就是挑选问题的一小部分。假设您有A，B和C组。您可以将其想象为：

permute(permute(A,B),C)

首先找到A和B的所有排列。获得该结果后，用C查找该结果的所有排列。四个组A，B，C，D可能看起来像：

permute(permute(permute(A,B),C),D)

等等。在此过程的每一步中，您都将获取当前的排列结果，并将其与输入的组列表中的下一个组进行排列。您一次只组合两个组，因此算法不必根据输入的组数进行更改。

在进行递归时，需要回答一些主要问题：

1. 您可以将问题递归分解为更小的，更可解决的问题吗？我认为以上示例证明了您可以做到。

2. 基本情况是什么？有什么解决方案将导致递归停止和展开？通常，递归可以逐步简化。在这种情况下，它可能归结为permute(A,{}){}是空集的地方。

3. 什么是递归情况？您将如何分解问题的一部分，并递归问题的较小子集？我认为最初的解释为您提供了一种可能的方式。只需一次拆分一组，然后将其与不断增长的结果进行置换即可。

当然，对于这个问题还有其他解决方案，这只是我脑海中的第一个解决方案。随着N越来越大，该算法将变得非常慢，因为它不是很有效。

因此，即使您不使用此解决方案，也希望它能使您走上正确的轨道！