java 递归算法在Java中查找集合的组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6966137/
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
Recursive Algorithm to find Combinations of a set in Java
提问by Ahmet Ikras
I was trying to find some examples on how to find a given set's (may be string or array of integers) all combinations in Java. And I have came across this code piece (found in http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html. I have copied only the related parts in here.):
我试图找到一些关于如何在 Java 中找到给定集合（可能是字符串或整数数组）的所有组合的示例。我遇到了这段代码（在http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html 中找到。我在这里只复制了相关部分。）：
// print all subsets of the characters in s
public static void comb1(String s) { comb1("", s); }
// print all subsets of the remaining elements, with given prefix
private static void comb1(String prefix, String s) {
if (s.length() > 0) {
System.out.println(prefix + s.charAt(0));
comb1(prefix + s.charAt(0), s.substring(1));
comb1(prefix, s.substring(1));
}
}
// read in N from command line, and print all subsets among N elements
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
String elements = alphabet.substring(0, N);
// using first implementation
comb1(elements);
System.out.println();
}
But, I really do not understand how it works. Does anyone care to explain?
但是，我真的不明白它是如何工作的。有人愿意解释吗？
采纳答案by rajah9
Java programs start at main. This one takes an argument which should be an integer. It stores the integer in N. If the user typed in java and the program name with 3, then N would be set to 3. This is used to peel off the first N letters of alphabet and place them in elements. (In our example, abc). Then it calls comb1(abc), that is, the public comb1 listed first.
Java 程序从 main 开始。这个需要一个参数，它应该是一个整数。它将整数存储在 N 中。如果用户在 java 中输入程序名称3，然后将 N 设置为 3。这用于剥离字母表的前 N 个字母并将它们放在元素中。（在我们的示例中，abc）。然后调用comb1( abc)，即首先列出的公共comb1。
Next comb1 calls the private comb1 with two arguments, an empty string and abc.
接下来comb1 使用两个参数调用私有comb1，一个空字符串和abc。
Now the recursion begins. Private comb1 takes a prefix and a string (in the first case an empty string and abc). If the string is not empty then it:
现在递归开始。私有 comb1 采用前缀和字符串（在第一种情况下为空字符串和abc）。如果字符串不为空，则它：
- prints the first char
- calls itself recursively with the prefix + the first char as the new prefix and remainder as the new string and
- calls itself recursively with the same prefix as new prefix and all but the first character as the new string.
- 打印第一个字符
- 以前缀+第一个字符作为新前缀，余数作为新字符串递归调用自身，并且
- 使用与新前缀相同的前缀和除第一个字符以外的所有字符作为新字符串递归调用自身。
(Here is where many people will tremble slightly… stare at it, hang on, be the computer, and the meaning will come.)
（这里是很多人会微微颤抖的地方……盯着看，撑住，当电脑，意义就来了。）
(Top level)
comb1("", "abc") -> *1* a *2* comb1("a", "bc") *3* comb1("", "bc")
(Second level)
comb1("a", "bc") -> *1* ab *2* comb1("ab", "c") *3* comb1("a", "c")
comb1("", "bc") -> *1* b *2* comb1("b", "c") *3* comb1("", "c")
(Third level)
comb1("ab", "c") -> *1* abc *2* comb1("abc", "") *3* comb1("ab", "")
comb1("a", "c") -> *1* ac *2* comb1("a", "") *3* comb1("a", "")
comb1("b", "c") -> *1* bc *2* comb1("bc", "") *3* comb1("b", "")
comb1("", "c") -> *1* c *2* comb1("c", "") *3* comb1("", "")
(Fourth level)
comb1("ab", "") -> (immediate return, ending recursion)
comb1("a", "") -> (immediate return, ending recursion)
comb1("b", "") -> (immediate return, ending recursion)
comb1("", "") -> (immediate return, ending recursion)
回答by Karoly Horvath
Creating all combinations of a given set is really simple. You have N elements, in each of the combinations an element is either present or not, so you have 2^N combinations. That recursive function does exactly that. It picks each element from that list and creates combinations which contain it and creates combintations which don't. Note: it does not print out the empty combination.
创建给定集合的所有组合非常简单。您有 N 个元素，在每个组合中都有一个元素存在或不存在，因此您有 2^N 个组合。该递归函数正是这样做的。它从该列表中选取每个元素并创建包含它的组合并创建不包含它的组合。注意：它不会打印出空组合。
If it's still not clear, create a short test string (eg: 3 characters), fire a debugger and see how it works.
如果仍然不清楚，请创建一个简短的测试字符串（例如：3 个字符），启动调试器并查看它是如何工作的。
