如何在 Java 中的任意数字组上创建笛卡尔积？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10262215/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to create cartesian product over arbitrary groups of numbers in Java?
提问by gomisha
Let's say I have 2 groups of numbers:
假设我有两组数字：
{1, 2, 3},
{4, 5}
I'd like to create an algorithm (in Java) that outputs the following 6 combinations:
我想创建一个算法（在 Java 中），输出以下 6 种组合：
1,4
1,5
2,4
2,5
3,4
3,5
There can be an arbitrary number of groups and an arbitrary number of members within each group. So in the above example, there are 2 groups with the first group having 3 members and the second group having 2 members. Another example is the following (3 groups, 3 members in first groups and 2 members in second and third groups):
可以有任意数量的组，每个组内可以有任意数量的成员。所以在上面的例子中，有 2 个组，第一个组有 3 个成员，第二个组有 2 个成员。另一个示例如下（3 个组，第一组 3 名成员，第二和第三组 2 名成员）：
{1, 2, 3},
{4, 5},
{6, 7}
Which would yield the following 12 combinations:
这将产生以下 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
How can I do this in Java? I'm trying to use recursion and I've looked at a similar questionalready but I'm still coming up short. Thanks for the help! (P.S. this is not for a homework assignment)
我怎样才能在 Java 中做到这一点？我正在尝试使用递归，我已经看过一个类似的问题，但我仍然不够用。谢谢您的帮助！（PS这不是家庭作业）
回答by Tudor
Got a bit bored and decided to give it a shot. Should be exactly what you need:
有点无聊，决定试一试。应该正是您所需要的：
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);
}
}
}
回答by Louis Wasserman
If you can use libraries, Guava'sSets.cartesianProduct(List<Set<E>>)does exactlywhat you're looking for. (Disclosure: I contribute to Guava.)
如果您可以使用库，GuavaSets.cartesianProduct(List<Set<E>>)可以完全满足您的需求。（披露：我为番石榴做出了贡献。）
回答by Brent Writes Code
One possible approach (not necessarily the most efficient) might be to take a divide and conquer approach. It's relatively simple to find all the permutations of two groups (the dumbest way is just nested for loops). Let's say you write a function called permuteand it does permute(A,B)where A (e.g. {(1), (2), (3)}) and B (e.g. {(4), (5)} are groups of numbers and it returns you all the permutations of A & B as a single group (e.g {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)}).
一种可能的方法（不一定是最有效的）可能是采用分而治之的方法。找到两个组的所有排列相对简单（最笨的方法就是嵌套 for 循环）。假设您编写了一个名为的函数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)}） .
So when you have N groups instead of 2, the easiest thing to do is just pick off small portions of the problem. Let's say you have groups A, B and C. Rather than worrying about them all separately, you can think of it as something like:
因此，当您有 N 个组而不是 2 个组时，最简单的方法就是挑出问题的一小部分。假设您有 A、B 和 C 组。与其分别担心它们，您可以将其视为以下内容：
permute(permute(A,B),C)
permute(permute(A,B),C)
Find all the permutations of A and B first. Once you have that result, find all the permutations of that result with C. And four groups A, B, C, D might look like:
首先找出 A 和 B 的所有排列。得到该结果后，用 C 找出该结果的所有排列。四组 A、B、C、D 可能如下所示：
permute(permute(permute(A,B),C),D)
permute(permute(permute(A,B),C),D)
And so on. At each step along the way, you take the current permutation result and permute it with the next group in the list of groups that you got as input. You're only ever combining two groups at a time, so the algorithm doesn't have to change depending on the number of groups you get as input.
等等。在此过程中的每一步，您获取当前的排列结果并将其与您作为输入获得的组列表中的下一组进行排列。您一次只能组合两个组，因此算法不必根据您作为输入获得的组数而改变。
When you're doing recursion, there are a few major questions you need to answer:
在进行递归时，您需要回答几个主要问题：
Can you recursively break down the problem into smaller, more solvable problems? I think the examples above prove that you can.
What is the base case? What is the solution that will cause the recursion to stop and unwind? It should generally be something really simple that your recursion can work down towards. In this case, it probably comes down to something like
permute(A,{})where {} is the empty set.What is the recursive case? How will you break off a chunk of the problem and recurse on a smaller subset of the problem? I think the initial explanation gives you one way of potentially doing this. Just break off one group at a time and permute it with your ever-growing result.
你能递归地把问题分解成更小、更容易解决的问题吗？我认为上面的例子证明你可以。
什么是基本情况？导致递归停止和展开的解决方案是什么？它通常应该是您的递归可以解决的非常简单的事情。在这种情况下，它可能归结为
permute(A,{}){} 是空集。什么是递归情况？您将如何分解问题的一部分并递归解决问题的较小子集？我认为最初的解释为您提供了一种可能做到这一点的方法。一次只拆分一组，然后用你不断增长的结果排列它。
There are certainly other solutions to this problem, this is just the first that popped into my head. As N gets bigger and bigger, this algorithm will get prohibitively slow since it's not very efficient.
这个问题当然还有其他解决方案，这只是我脑海中出现的第一个。随着 N 越来越大，这个算法会变得非常慢，因为它不是很有效。
So even if you don't use this solution, I hope it gets you on the right track!
因此，即使您不使用此解决方案，我也希望它能让您走上正轨！
回答by erikxiv
How about the following pseudo code (w/o recursion)
下面的伪代码怎么样（不带递归）
// 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
