Created
January 13, 2014 04:57
-
-
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).
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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