Skip to content

Instantly share code, notes, and snippets.

@shaunlebron
Created May 31, 2012 15:00
Show Gist options
  • Save shaunlebron/2843980 to your computer and use it in GitHub Desktop.
Save shaunlebron/2843980 to your computer and use it in GitHub Desktop.
Iterating Combinations

Iterating Combinations

If you're trying to iterate all combinations of k=5 on n=36, this is how you loop through them.

int k = 5;
int n = 36;
int count = 0;
for (int i1=1;    i1 <= n-k+1; i1++)
for (int i2=i1+1; i2 <= n-k+2; i2++)
for (int i3=i2+1; i3 <= n-k+3; i3++)
for (int i4=i3+1; i4 <= n-k+4; i4++)
for (int i5=i4+1; i5 <= n-k+5; i5++)
    printf("%d: %d %d %d %d %d\n", ++count, i1,i2,i3,i4,i5);

This is the simplest way to generate them, using a manual for-loop for each value in k. You can write a script to generate these for-loops for any required values of k.

Dynamic Solutions

This can be implemented dynamically with recursion, shown in 'recurse_combinations.c'.

This can also be implemented dynamically using next-state heuristics, shown in 'next_combination.c'.

Speed

The number of combinations are astronomical for all but the smallest values of k. So the time to complete is going to be very long for sufficiently sized values of k, regardless of the chosen generator solution. (I wasn't able to determine which performed better as they responded differently to different optimization flags specific to the gcc compiler.)

#include <stdio.h>
int main()
{
int k = 5;
int n = 36;
int count = 0;
int i1,i2,i3,i4,i5;
for (i1=1; i1 <= n-k+1; i1++)
for (i2=i1+1; i2 <= n-k+2; i2++)
for (i3=i2+1; i3 <= n-k+3; i3++)
for (i4=i3+1; i4 <= n-k+4; i4++)
for (i5=i4+1; i5 <= n-k+5; i5++)
printf("%d: %d %d %d %d %d\n", ++count, i1,i2,i3,i4,i5);
return 0;
}
#include <stdio.h>
// 'values' indicates a valid combination:
// e.g. 11000111 is represented with values=[1,2,6,7,8]
// with k=5, n=8.
//
// If initially values=[1,..,k], then applying this
// function successively will generate all combinations.
// A return value of 0 will be given when done
int next_combination(int *values, int k, int n)
{
// identify the rightmost index that can be shifted to the right
// e.g. 11000111
// ^
int i = k-1;
if (values[i] == n) {
i--;
while (i >= 0 && values[i] == values[i+1]-1)
i--;
}
// exit if no more combinations can be made
// e.g. 00011111
if (i==-1)
return 0;
// shift chosen index to the right
// e.g.
// (before: 11000111)
// ^
// (after: 10100111)
// ^
values[i]++;
// left-collapse any following indexes
// (before: 10100111)
// ^ ***
// (after: 10111100)
// ^***
i++;
while (i < k) {
values[i] = values[i-1]+1;
i++;
}
return 1;
}
// Calculate the number of combinations of k over n elements.
// (equal to binomial coefficient, or 'n choose k')
unsigned long long num_combinations(int k, int n)
{
unsigned long long num = 1;
int i;
for (i=0; i<k; i++)
num *= (n-i);
for (i=2; i<=k; i++)
num /= i;
return num;
}
int main()
{
// determine that we want combinations of k over n elements
const int n = 36;
const int k = 3;
// create initial combination
// (e.g. values = [1,2,...,k]
int values[k];
int i;
for (i=0; i<k; i++)
values[i] = i+1;
// enumerate the other combinations
unsigned long long count = 0;
do {
// increment combination count
count++;
// print combination (this will be very slow for higher values of k)
printf("%llu: ", count);
for (i=0; i<k; i++)
printf("%d ", values[i]);
printf("\n");
}
while (next_combination(values, k, n));
// print actual and expected counts (should match)
printf("actual: %llu\n",count);
printf("expected: %llu\n",num_combinations(k,n));
return 0;
}
#include <stdio.h>
// determine that we want combinations of k over n elements
#define k 3
#define n 36
// 'values' indicates a valid combination:
// e.g. 11000111 is represented with values=[1,2,6,7,8]
// with k=5, n=8.
int values[k];
// running total of combinations created
unsigned long long count = 0;
// If called with start_value=1 and start_index=0,
// all combinations of k over n elements will be printed.
void recurse_combinations(int start_value, int start_index)
{
int i,j;
i = start_index;
for (values[i] = start_value; values[i] <= n-k+start_index+1; values[i]++) {
if (start_index == k-1) {
// increment combination count
count++;
// print combination
printf("%llu: ", count);
for (j=0; j<k; j++)
printf("%d ", values[j]);
printf("\n");
}
else {
recurse_combinations(values[i]+1, start_index+1);
}
}
}
int main()
{
recurse_combinations(1, 0);
printf("%llu\n", count);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment