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

Question

比方说，我有2组数字：

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

我想创建的算法（在Java中）输出以下6种组合：

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

可以有任意数量的的团体和任意数量的成员在每个组内。所以在上面的例子中，有两个组，第一组有三个成员，第二组有两个成员。另一个例子是下面的（3组，在第一组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中？我正在尝试使用递归，我已经看了一个similar question，但我仍然缺乏。谢谢您的帮助！ （P.S.这不是一个家庭作业）

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

一个可能的方法（不一定是最有效的）可能是采取分而治之的方法。找到两个组的所有排列相对简单（最笨的方法只是嵌套循环）。假设你写了一个叫做permute的函数，它的确有permute(A,B)这里A（例如{（1），（2），（3）}）和B（例如{（4），（5）}是数组，并且它返回（例如{（1,4），（1,5），（2,4），（2,5），（3,4），（3,5））作为单个组的A & B的所有排列}）

所以当你有N个组而不是2个时，最简单的事情就是挑出一小部分问题，假设你有组A，B和C，而不是单独担心它们，你可以把它看成是这样的：

permute(permute(A,B),C)

寻找的所有排列和B先。一旦你的结果，找到C。和四组A，B，C是结果的所有排列，d可能看起来像：

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

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

当你在做递归，有一个你需要回答几个主要问题：

1. 你能递归分解问题分解成更小，更可解决的问题？我认为上面的例子证明你可以。

2. 什么是基本情况？什么是会导致递归停止和放松的解决方案？它通常应该是非常简单的事情，你的递归可以减少。在这种情况下，它可能归结为permute(A,{})，其中{}是空集。

3. 什么是递归情况？你将如何解决这个问题的一大块，并缓解一小部分问题？我认为最初的解释为您提供了一种可能的方式。只需一次拆除一个组，并以不断增长的结果进行排列。

当然有这个问题的其他解决方案，这仅仅是出现在我头上的第一。随着N变得越来越大，这种算法会变得过于缓慢，因为它效率不高。

所以即使你不使用这个解决方案，我希望它能让你走上正轨！

Answer 3

如何以下伪代码（W/O递归）

// Create the initial result filled with the first set of numbers 
List result = new List() 
For each number in the first set 
    result.add(new List(number)) 

// Iterate over the following sets to permutate over 
For each remaining set S 
    List newResult = new List() 
    For each list L in result 
    For each number N in S 
     newResult.add(copy of L with N added) 
    result = newResult 

Answer 4

如果你可以使用图书馆，Guava'sSets.cartesianProduct(List<Set<E>>)不正是你在找什么。 （披露：我贡献番石榴。）