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