Combination encoder / decoder

comb.c

/**** combination (n choose k) encoder / decoder ****
 *                                                  *
 * a k-combination {c1,...,ck} of {0,1,...,n-1} can *
 * be encoded as C(c1,1) + C(c2,2) + ... + C(ck,k). *
 *                                                  *
 ****************************************************/

#include <stdio.h>
#include <assert.h>

unsigned choose(unsigned n, unsigned k)
{
	unsigned t = 1;
	unsigned i;

	if (k > n)
		return 0;
	if (k+k > n)
		k = n - k;
	for (t = i = 1; i <= k; i++)
		t = (unsigned long) t * (n-i+1) / i;
	return t;
}

void decode(unsigned S[], unsigned n, unsigned k, unsigned code)
{
	unsigned t;

	assert(code < choose(n, k));
	while (k > 0) {
		while ((t = choose(--n, k)) > code)
			;
		code -= t;
		S[--k] = n;
	}
}

unsigned encode(const unsigned S[], unsigned n, unsigned k)
{
	unsigned code = 0;

	assert(n >= k);
	while (k > 0) {
		assert(S[k-1] < n);
		code += choose(S[k-1], k);
		--k;
	}
	return code;
}

#ifndef N
# define N 5
#endif

void print_subsets(unsigned k)
{
	unsigned S[N];
	unsigned m, i, code;

	printf("Subset of {0..%u} of %u elements.\n", N-1, k);
	m = choose(N, k);
	for (code = 0; code < m; code++) {
		decode(S, N, k, code);
		for (i = 0; i < k; i++)
			printf("%d%c", S[i], (i == k-1) ? '\t' : ' ');
		printf("; code = %u\n", code);
		assert(encode(S, N, k) == code);
	}
}

int main()
{
	unsigned k;

	for (k = 0; k <= N; k++)
		print_subsets(k);
}