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.