CODEWITHSUNDEEP
javarecursioncombinations
Ahmet Ikras
Ahmet Ikras

Reputation: 23

Recursive Algorithm to find Combinations of a set in Java

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?

Upvotes: 1

Views: 10749

Answers (2)

rajah9
rajah9

Reputation: 12329

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:

  1. prints the first char
  2. calls itself recursively with the prefix + the first char as the new prefix and remainder as the new string and
  3. 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)

Upvotes: 0

Karoly Horvath
Karoly Horvath

Reputation: 96258

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.

Upvotes: 3

Related Questions