NOTICE ISP is back up.. Stay tuned for class status for Thursday 2017-03-23
Free Java Tutorials >> Table of contents >> Combinatorics

1. Combinations

What are combinations?

Let's say you have a red ball, a green ball, and a blue ball. We can label them RGB. Combinations allow us to determine all the different subsets we could possibly have. For subsets of size one, we could have just one R, one G, or one B. For subsets of size two, we could have RG, GB, and RB. Order does not matter when determining combinations, and so RG is the same as GR. Finally, there is only one set of size three, which is RGB. Notice there is also only one subset of size zero, which is no balls

Because order doesn't matter, every combination can be described as a series of booleans. In our previous example there would be three booleans: do we include the red ball? do we include the green ball? do we include the blue ball? As a result, we can describe each combination as a binary number. 000 represents the empty set of no balls. 001 is just the blue ball. 010 is just the green. 011 is the green and the blue, 100 is the red by itself. 101 is red and blue. 110 is red and green. 111 is all three. Notice that if we have 3 items, the length of the binary number is 3. We count from 000 to 111 to obtain each combination, and the total number of combinations is two to the power of three.

Because every combination can be described as a binary number, there is also an elegant non-recursive way of going through every single combination: count in binary. However, if we would like to only include combinations of a certain length, the recursive method may be preferable

Combinations of characters in a string

To write a recursive algorithm that determines combinations, we start by creating an empty boolean array of length equal to the number of items. In the following example, we're going to try every combination of each character in "ABC", so we will create a boolean array of length 3.

Next, the recursive algorithm will pick whether or not to include the first character. For either possible, (including and not including), we will recursively decide whether or not to include the second character. For both of those two paths again we will try either including or not including the third character. When we get to the end of the string (pos==inc.length in the following example), then we stop recursion:

public class MyProgram {
    public static void main(String[] args) {
		comb("ABC",new boolean[3],0);
    }
	//use bool array to say include/or not
	static void comb(String x, boolean[] inc, int pos){
		if(pos==inc.length) {                   //we reached the end
			for(int i=0;i<inc.length;i++) {
				if(inc[i]) System.out.print(x.charAt(i));  //print each character we include
			}
			System.out.println(); return;   //exit
		}
		inc[pos] = true;    //include this character
		comb(x,inc,pos+1);  //recurse
		inc[pos] = false;   //do not include this character
		comb(x,inc,pos+1);  //recurse
	} 
}
//outputs ABC,AB,AC,A,BC,B,C

An example of combinations with a String array

We could have used Strings in a string array rather than characters in string. This example will output "aardvark badger crab","aardvark badget","aardvark crab","aardvark","badger crab","badger","crab":

public class MyProgram {
    public static void main(String[] args) {
		String[] animals = {"aardvark","badger","crab"};
		comb2(animals,new boolean[3],0);
    }
	static void comb2(String[] x, boolean[] inc, int pos) {
		if(pos == inc.length) {
			for(int i=0;i<inc.length;i++) {
				if(inc[i]) System.out.print(x[i]+" ");
			}
			System.out.println();
			return;
		}
		inc[pos] = true;
		comb2(x,inc,pos+1);
		inc[pos] = false;
		comb2(x,inc,pos+1);
	}
}

Because this is so similar to the example with letters in a String, we will be using letters in a string for all of the following examples. Please note however that you can modify the first argument of the recursive function to be any kind of array like structure.

Limiting to combinations of a certain length

So far we've been printing every combination. However, sometimes we want to only have combinations of a certain size. An example problem might be: you have three friends but you can only bring two of them with you to your free boat tour. You are given a function that returns how much happiness you will get depending on which friends you bring. Determine which friends you bring.

In this problem, we could enumerate the three friends as ABC. Then we could get every length two combination like so:

public class MyProgram {
    public static void main(String[] args) {
		comb3("ABCDE", 3);
    }
	//Helper function so we can use default arguments
	static void comb3(String x, int targetlength) {
		comb3(x, new boolean[x.length()], 0, 0, targetlength);
	}

	//The new arguments are included and targetlength
	//We keep track of how many characters long our subset is,
	//and we stop when we reach targetlength
	static void comb3(String x, boolean[] inc, int pos, int included, int targetlength) {
		if (included == targetlength) {
			//Rather than printing, we could calculate 
			//how much happiness these friends give us:
			for (int i=0;i<inc.length;i++) {
				if (inc[i]) System.out.print(x.charAt(i));  
			}
			System.out.println(); 
			return;   //exit
		}
		if (pos >= inc.length) return;
		inc[pos] = true; 
		comb3(x, inc, pos+1, included+1, targetlength); //+1 because we included another
		inc[pos] = false; 
		comb3(x, inc, pos+1, included, targetlength); 
	} 
}
//outputs:
//ABC
//ABD
//ABE
//ACD
//ACE
//ADE
//BCD
//BCE
//BDE
//CDE

The main difference here is that we keep track of how many characters we've included. When we reach our target, we stop rather than keep going.

Advanced students should recognize there is an optimization possible here. We can quit early if we know that even if we included all the following letters, we would still not reach our target. If we are at the position pos, then there are inc.length - pos remaining letters. This number needs to be greater than or equal to targetlength - included. If not, we can return.



			
Run

2. Variations

What are variations?

The variations of ABC with length 2 are: AA,AB,AC,BA,BB,BC,CA,CB,CC. In simple english, we are allowed any of the three characters for our first choice, and we are allowed to still take any of the three characters fo the second choice. When computing the variations of length n, the number of variations is equal to the number of choices (here 3) to the power of the length (n). So with ABC and 2, it's three to the power of two, or nine.

Thus each time the algorithm recurses, we use a for loop to try recursing with every single possible additional character. Here's the completed code:

public class MyProgram {
    public static void main(String[] args) {
		variations("ABC","",2); 
    }
	static void variations(String x, String pre, int len) {
		if(len==0) { 
			System.out.println(pre); 
			return; 
		}
		for(int i=0;i<x.length();i++) {
			String p = pre+x.charAt(i);
			variations(x,p,len-1);
		}
	} //note recursive does not remove items
	//outputs AA,AB,AC,BA,BB,BC,CA,CB,CC
}
//If we ran it for XY with length of 3, the execution would look like:
//v("XY","",3)
//  v("XY","X",2)
//    v("XY","XX",1)
//      v("XY","XXX",0) prints "XXX"
//      v("XY","XXY",0) prints "XXY"
//    v("XY","XY",1)
//      v("XY","XYX",0) prints "XYX"
//      v("XY","XYY",0) prints "XYY"
//  v("XY","Y",2)
//    v("XY","YX",1)
//      v("XY","YXX",0) prints "YXX"
//      v("XY","YXY",0) prints "YXY"
//    v("XY","YY",1)
//      v("XY","YYX",0) prints "YYX"
//      v("XY","YYY",0) prints "YYY"

Again, it would require only a small number of changes to modify the function to support arrays or other data structures rather than a String.



			
Run

3. Permutations

What are Permutations?

Permutations are like variations, except we are not allowed to repeat an item within the same subset. For example, permutations of ABC of length 3 are ABC,ACB,BAC,BCA,CAB,CBA. The permutations algorithm is very similar to the variations algorithm, except when we "pick" a character, we must also remove it from the set of possible characters we may use:

public class MyProgram {
    public static void main(String[] args) {
		perm("ABC","",3); 
    }
	static void perm(String x, String pre, int len) {
		if(len==0) { 
			System.out.println(pre); 
			return; 
		}
		for(int i=0;i<x.length();i++) {
			String p = pre+x.charAt(i);
			
			//this line removes the character at position i:
			String c = x.substring(0,i)+x.substring(i+1);
			perm(c,p,len-1);
		}
	}
}
//outputs ABC,ACB,BAC,BCA,CAB,CBA

//The execution path is:
//perm("ABC","",3);
//  perm("BC","A",2);
//    perm("C","AB",1);
//      perm("","ABC",0); prints "ABC"
//    perm("B","AC",1);
//      perm("","ACB",0); prints "ACB"
//  perm("AC","B",2);
//    perm("C","BA",1);
//      perm("","BAC",0); prints "BAC"
//    perm("A","BC",1);
//      perm("","BCA",0); prints "BCA"
//  perm("AB","C",2);
//    perm("B","CA",1);
//      perm("","CAB",0); prints "CAB"
//    perm("A","CB",1);
//      perm("","CBA",0); prints "CBA"


			
Run

Previous: Flood Fill

Next: Recursive Sort