Generate Combinations

• Tweet
• 

        Code generates all the combinations of n elements choosing k elements.

See <a href="http://mathworld.wolfram.com/Combination.html">this</a> for definition.

See <a href="http://compprog.wordpress.com/2007/10/17/generating-combinations-1/">this</a> for explanation</a>.

#include <stdio.h>

/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
	printf("{");
	int i;
	for (i = 0; i < k; ++i)
		printf("%d, ", comb[i] + 1);
	printf("\b\b}\n");
}

/*
	next_comb(int comb[], int k, int n)
		Generates the next combination of n elements as k after comb

	comb => the previous combination ( use (0, 1, 2, ..., k) for first)
	k => the size of the subsets to generate
	n => the size of the original set

	Returns: 1 if a valid combination was found
		0, otherwise
*/
int next_comb(int comb[], int k, int n) {
	int i = k - 1;
	++comb[i];
	while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
		--i;
		++comb[i];
	}

	if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
		return 0; /* No more combinations can be generated */

	/* comb now looks like (..., x, n, n, n, ..., n).
	Turn it into (..., x, x + 1, x + 2, ...) */
	for (i = i + 1; i < k; ++i)
		comb[i] = comb[i - 1] + 1;

	return 1;
}

int main(int argc, char *argv[]) {
	int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
	int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
	int comb[16]; /* comb[i] is the index of the i-th element in the
			combination */

	/* Setup comb for the initial combination */
	int i;
	for (i = 0; i < k; ++i)
		comb[i] = i;

	/* Print the first combination */
	printc(comb, k);

	/* Generate and print all the other combinations */
	while (next_comb(comb, k, n))
		printc(comb, k);

	return 0;
}

Tags:
• algorithm
• C
• combinations
• combinatorics
• example
• generate

Comments

Jerry Wilcox replied on Sat, 2009/05/30 - 9:28pm

Thanks for this algorithm. There is, however, a minor bug in the code. You can see it happen by printing out the value of 'n' before returning from your main. If you do, you'll see that 'n' ends up with the value of '6' rather than remaining at '5' as it should. When you make the next_comb call after the final valid combination has been generated, your code increments the value of comb[-1], which at least on my Mac OS X machine increments the value of 'n'. The offending code is at the beginning of next_comb: while ((i >= 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } The first test in the 'while' (i >= 0) should simply be (i > 0), making the modified code read while ((i > 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } I've done quite a bit of testing of this change and all of my test cases have worked.

• Login or register to post comments