DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

# Generate Combinations

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; }

## Comments

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

`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.