Java 中查找集合组合的递归算法
我试图找到一些关于如何在 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();
}
但是，我真的不明白它是如何工作的。有人愿意解释一下吗？
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.):
// 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
创建给定集合的所有组合非常简单。您有 N 个元素，每个组合中都有一个元素存在或不存在，因此您有 2^N 种组合。该递归函数正是这样做的。它从该列表中选取每个元素并创建包含该元素的组合，并创建不包含该元素的组合。注意：它不会打印出空组合。
如果仍然不清楚，请创建一个短测试字符串（例如：3 个字符），启动调试器并查看其工作原理。
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.
If it's still not clear, create a short test string (eg: 3 characters), fire a debugger and see how it works.
Java 程序从 main 开始。这个参数需要一个整数。它将整数存储在N中。如果用户输入java并且程序名称带有
3，那么N将被设置为3。这用于剥离字母表的前N个字母并将它们放置在元素中。 （在我们的示例中，abc）。然后它调用comb1(abc)，即首先列出的公共comb1。接下来comb1 使用两个参数（一个空字符串和
abc）调用私有comb1。现在递归开始。私有的comb1需要一个前缀和一个字符串（在第一种情况下是一个空字符串和
abc）。如果字符串不为空，则：（这里很多人会微微颤抖……盯着它，坚持住，成为电脑，意义就会来。）
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.Next comb1 calls the private comb1 with two arguments, an empty string and
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:(Here is where many people will tremble slightly… stare at it, hang on, be the computer, and the meaning will come.)