Combinations in lexicographic order

Combinations of size k

Prints out all C(n, k) = n! / (k! * (n-k)!) combinations of size k in increasing lexicographic order.

For example: From a given String “abcde” when n = 5 and k = 3 you should get the following output:

abc abd abe acd ace ade bcd bce bde cde

Solution: Using arrays instead of String. I referred to a good recursive implementation of Robert Sedgewick and Kevin Wayne.

/**
	 * Enumerates all subsets of size k on N elements.
	 * @param s array having size k
	 * @param position keep tracking position
	 * @param nextInt next generation
	 * @param k size k
	 * @param N number of elements
	 */
	public static void generate(int[] s, int position, int nextInt, int k, int N) {
		if (position == k) {
			showCombination(s);
			return;
		}
		for (int i = nextInt; i < N; i++) {
			s[position] = i;
			generate(s, position + 1, i + 1, k, N);
		}
	}

	private static void showCombination(int[] s) {
		for (int i = 0; i < s.length; i++)
			System.out.print(s[i] + " ");
		System.out.println();
	}

	public static void main(String[] args) {
		int N = 5;
		int k = 3;

		int[] s = new int[k];
		generate(s, 0, 0, k, N);
	}
	

Output in console of 10 combination numbers:

0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 

Combinations

Prints out all 2^n combinations of any size. For instance, From given String “abc” when n = 3 you should get the following output:

a ab abc ac b bc c

Solution:

/** Recursive approach to generate all combination size k.
*   Counting from 0 to 2^N - 1
*/
public static void generate2(String prefix, String s){
		System.out.println(prefix);
		for (int i = 0; i < s.length(); i++){
			generate2(prefix + s.charAt(i), s.substring(i + 1));
		}
	}
public static void main(String[] args) {
		String str = "abc";
		generate2("",str);
	}

 
Output in console:

a
ab
abc
ac
b
bc
c

References:

1. Robert Sedgewick, and Kevin Wayne, Recursion, In “Introduction to Programming in Java”, latest update Nov 03, 2015. Accessed on May 2nd, 2016. http://introcs.cs.princeton.edu/java/23recursion/
2. Frank Ruskey, Lexicographic Algorithms, In “Compinational Generation”. pp.55-66 Octorber 1, 2003, University of Victoria. [1]