# Combinations in lexicographic order

By | May 2, 2016

### 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]

This site uses Akismet to reduce spam. Learn how your comment data is processed.