Recursive Algorithm to find Combinations of a set in Java

Question

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?

Is it the code you're having problems with, or is it the basic principle? You might want to take a pencil and paper and walk through a small sample. Start with N=2 and follow what the code does with "abc". — Bart
– Bart, Commented Aug 6, 2011 at 10:22

Karoly Horvath · Accepted Answer · 2011-08-06 10:35:48Z

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.

edited Aug 6, 2011 at 10:35

answered Aug 6, 2011 at 10:26

Karoly Horvath

96.7k11 gold badges123 silver badges181 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rajah9 · Accepted Answer · 2011-08-06 11:10:32Z

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:

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)

Collectives™ on Stack Overflow

Recursive Algorithm to find Combinations of a set in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related