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:

- Find the rightmost element
`ar[i]`that is less than the maximum value it can have (which is (`n`– 1) – (`k`– 1) –`i`) - Increment it
- 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; }