Tag Archives: Combinations

Combinations of a multiset

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:

  1. 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).
  2. Replace it with the first multiset element greater than it.
  3. 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;
}

Combinations

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:

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