Iterating Combinations

README.md

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

manual_combinations.c

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

next_combination.c

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

recurse_combinations.c

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