These are the combinations of k elements chosen from a set that can contain duplicates (a multiset).
For example, given the multiset {0, 1, 1, 2, 2, 2, 3}, the 4-combinations are:
[0, 1, 1, 2] [0, 1, 1, 3] [0, 1, 2, 2] [0, 1, 2, 3] [0, 2, 2, 2] [0, 2, 2, 3] [1, 1, 2, 2] [1, 1, 2, 3] [1, 2, 2, 2] [1, 2, 2, 3] [2, 2, 2, 3]
This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.
Begin with the first combination, which is the first k elements of the multiset ([0, 1, 1, 2] in the example above), and then at each step:
- Find the rightmost element that is less than the maximum value it can have (which is the element in the multiset that is the same distance from the right).
- Replace it with the first multiset element greater than it.
- Replace the remainder of the combination with the elements that follow the replacement in the multiset.
unsigned int next_multiset_combination(const unsigned int *multiset, unsigned int *ar, size_t n, unsigned int k) { unsigned int finished = 0; unsigned int changed = 0; unsigned int i; for (i = k - 1; !finished && !changed; i--) { if (ar[i] < multiset[i + (n - k)]) { /* Find the successor */ unsigned int j; for (j = 0; multiset[j] <= ar[i]; j++); /* Replace this element with it */ ar[i] = multiset[j]; if (i < k - 1) { /* Make the elements after it the same as this part of the multiset */ unsigned int l; for (l = i + 1, j = j + 1; l < k; l++, j++) { ar[l] = multiset[j]; } } changed = 1; } finished = i == 0; } if (!changed) { /* Reset to first combination */ for (i = 0; i < k; i++) { ar[i] = multiset[i]; } } return changed; }
Here is an example program:
#include <stdio.h> #include <multiset-combination.h> static void print_array(const unsigned int *ar, size_t len, FILE *fptr) { unsigned int i; fputc('[', fptr); for (i = 0; i < len; i++) { fprintf(fptr, "%d", ar[i]); if (i < len - 1) { fputs(", ", fptr); } } fputc(']', fptr); } int main(void) { unsigned int multiset[] = {0, 1, 1, 2, 2, 2, 3}; unsigned int n = sizeof(multiset) / sizeof(unsigned int); unsigned int numbers[] = {0, 1, 1, 2}; const unsigned int k = sizeof(numbers) / sizeof(unsigned int); do { print_array(numbers, k, stdout); putchar('\n'); } while (next_multiset_combination(multiset, numbers, n, k)); return 0; }
Here is a second example that prints the elements of the multisets:
#include <stdio.h> #include <multiset-combination.h> static void print_set(const unsigned int *ar, size_t len, const void **elements, const char *brackets, printfn print, FILE *fptr) { unsigned int i; fputc(brackets[0], fptr); for (i = 0; i < len; i++) { print(elements[ar[i]], fptr); if (i < len - 1) { fputs(", ", fptr); } } fputc(brackets[1], fptr); } int main(void) { unsigned int multiset[] = {0, 1, 1, 2, 2, 2, 3}; char *elements[] = {"a", "b", "c", "d"}; const size_t n = sizeof(multiset) / sizeof(unsigned int); unsigned int numbers[] = {0, 1, 1, 2}; const size_t k = sizeof(numbers) / sizeof(unsigned int); do { print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout); putchar('\n'); } while (next_multiset_combination(multiset, numbers, n, k)); return 0; }