# Multicombinations

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:

1. Find the rightmost element that is less than n – 1
2. Increment it.
3. 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;
}