A multicombination is a combination that can contain duplicates (i.e., the combination is a multiset).
Note that the source set does not contain duplicates. For combinations of a set that contains duplicates, see combinations of a multiset.
These are the 3-multicombinations of the 4-set {0, 1, 2, 3}:
[0, 0, 0] [0, 0, 1] [0, 0, 2] [0, 0, 3] [0, 1, 1] [0, 1, 2] [0, 1, 3] [0, 2, 2] [0, 2, 3] [0, 3, 3] [1, 1, 1] [1, 1, 2] [1, 1, 3] [1, 2, 2] [1, 2, 3] [1, 3, 3] [2, 2, 2] [2, 2, 3] [2, 3, 3] [3, 3, 3]
This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.
To find the next multicombination containing k elements from a set containing n elements, begin with the multicombination containing k zeroes, then at each step:
- Find the rightmost element that is less than n – 1
- Increment it.
- Make the elements after it the same.
unsigned int next_multicombination(unsigned int *ar, size_t n, unsigned int k) { unsigned int changed = 0; int i; for (i = k - 1; i >= 0 && !changed; i--) { if (ar[i] < n - 1) { /* Increment this element */ ar[i]++; if (i < k - 1) { /* Make the elements after it the same */ unsigned int j; for (j = i + 1; j < k; j++) { ar[j] = ar[j - 1]; } } changed = 1; } } if (!changed) { /* Reset to first combination */ for (i = 0; i < k; i++) { ar[i] = 0; } } return changed; }
Example program to produce the output above:
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 numbers[3] = {0}; const size_t k = sizeof(numbers) / sizeof(numbers[0]); unsigned int n = 4; do { print_array(numbers, k, stdout); putchar('\n'); } while (next_multicombination(numbers, n, k)); return 0; }