/**

* Here we present two methods (recursive and iterative) of generating all

* the combinations of a set by choosing only r of n elements.

*

* Time Complexity: O( n choose r )

*

* @author William Fiset, Micah Stairs

**/

public class Combinations {

// This method finds all the combinations of size r in a set

public static void combinationsChooseR(int[] set, int r) {

if (r < 0) return;

if (set == null) return;

boolean [] used = new boolean[set.length];

combinations(set, r, 0, used);

}

// To find all the combinations of size r we need to recurse until we have

// selected r elements (aka r = 0), otherwise if r != 0 then we need to select

// an element which is found after the position of our last selected element

private static void combinations(int[] set, int r, int at, boolean[] used) {

final int N = set.length;

// Return early if there are more elements left to select than what is available.

int elementsLeftToPick = N - at;

if (elementsLeftToPick < r) return;

// We selected 'r' elements so we found a valid subset!

if (r == 0) {

System.out.print("{ ");

for (int i = 0; i < N; i++)

if (used[i])

System.out.print(set[i] + " ");

System.out.println("}");

} else {

for (int i = at; i < N; i++) {

// Try including this element

used[i] = true;

combinations(set, r - 1, i + 1, used);

// Backtrack and try the instance where we did not include this element

used[i] = false;

}

}

}

// Use this method in combination with a do while loop to generate all the combinations

// of a set choosing r elements in a iterative fashion. This method returns

// false once the last combination has been generated.

// NOTE: Originally the selection needs to be initialized to {0,1,2,3 ... r-1}

public static boolean nextCombination(int[] selection, int N, int r) {

if (r > N) throw new IllegalArgumentException("r must be <= N");

int i = r - 1;

while (selection[i] == N - r + i)

if (--i < 0) return false;

selection[i]++;

for (int j = i + 1; j < r; j++) selection[j] = selection[i] + j - i;

return true;

}

public static void main(String[] args) {

// Recursive approach

int R = 3;

int[] set = {1,2,3,4,5};

combinationsChooseR(set, R);

// prints:

// { 1 2 3 }

// { 1 2 4 }

// { 1 2 5 }

// { 1 3 4 }

// { 1 3 5 }

// { 1 4 5 }

// { 2 3 4 }

// { 2 3 5 }

// { 2 4 5 }

// { 3 4 5 }

// Suppose we want to select all combinations of colors where R = 3

String[] colors = {"red", "purple", "green", "yellow", "blue", "pink"};

R = 3;

// Initialize the selection to be {0, 1, ... , R-1}

int[] selection = { 0, 1, 2 };

do {

// Print each combination

for (int index : selection)

System.out.print(colors[index] + " ");

System.out.println();

} while( nextCombination(selection, colors.length, R) );

// prints:

// red purple green

// red purple yellow

// red purple blue

// red purple pink

// red green yellow

// red green blue

// red green pink

// red yellow blue

// red yellow pink

// red blue pink

// purple green yellow

// purple green blue

// purple green pink

// purple yellow blue

// purple yellow pink

// purple blue pink

// green yellow blue

// green yellow pink

// green blue pink

// yellow blue pink

}

}