# Combinations

Combinations, or k-combinations, are the unordered sets of k elements chosen from a set of size n.

For example, there are 10 3-combinations of the 5-set {0, 1, 2, 3, 4}:

{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}


The set of all combinations 0 ≤ k ≤ n is the power set.

Combinations that can contain duplicates are called multicombinations.

Combinations of a set containing duplicates are combinations of a multiset.

Combinations where order is significant are called k-permutations.

This algorithm produces the combinations in lexicographic order, with the elements in each combination strictly increasing in magnitude.

Begin with the combination containing the the numbers from 0 to k – 1, and at each step:

1. Find the rightmost element ar[i] that is less than the maximum value it can have (which is (n – 1) – (k – 1) – i)
2. Increment it
3. Turn the elements after it into a linear sequence continuing from ar[i]
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;

if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}