Skip to content

Instantly share code, notes, and snippets.

@Prince781
Created January 13, 2014 04:57
Show Gist options
  • Select an option

  • Save Prince781/8394985 to your computer and use it in GitHub Desktop.

Select an option

Save Prince781/8394985 to your computer and use it in GitHub Desktop.
One solution to the issue of finding the amount of combinations for k elements in a list of length n. (See http://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations).
// k_elements_from_n
// c99
#include <stdio.h>
#include <stdlib.h>
unsigned long factorial(long n) {
return n==1 ? 1 : n*factorial(n-1);
}
void print_arr(int arr[], int length) {
for (int i=0, l=length; i<l; i++)
printf("%s%d%s", i==0?"[":"", arr[i], i+1<l?", ":"]\n");
}
// Combo of k elements from n-list; results are printed out
void comb(int k, int n) {
if (k > n) return;
int group[k];
printf("Task: find %d items from a list of %d elements.\n", k, n);
printf("There are %d!/(%d!%d!) = %lu possible combinations.\n",
n, k, n-k, factorial(n)/(factorial(k)*factorial(n-k)));
// initialize group
for (int i=0; i<k; i++)
group[i] = i+1;
int iter = 0;
printf("%d. ", ++iter);
print_arr(group, k);
for (int p=k-1; p>=0;) { // e[p] at limit
if (group[p] == n-(k-p-1)) p--;
else if (p+1<k && group[p+1] == n-(k-p-2)) {
group[p]++; // e[p] not at limit, but e[p+1] is
group[p+1] = group[p];
p++;
} else {
group[p]++; // neither; continue to increment e[p]
printf("%d. ", ++iter);
print_arr(group, k);
}
}
}
int main(int argc, char* argv[]) {
if (argc > 2)
for (int a=1; a+1<argc; a+=2)
comb(atoi(argv[a]), atoi(argv[a+1]));
else comb(4, 12); // example
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment