# Generating (all) combinations efficiently

This is just a C-implementation of the previous post.

```
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>

/* Logical defines */
#define TRUE  			1
#define FALSE 			0

/*
************************************************************************

COMBINATION

Create a combination of [length] of Hamming weight [weight].

Based on the algorithm description given in Knuth's Art of
Computer Programming. In order for the implementation to be
efficient, compiler inlining is recommended.

Carl Löndahl, 2012

*/

typedef struct permuation {

uint16_t*			index;
size_t				length, weight;

} permutation;

combination* new_perm(size_t length, size_t weight) {

uint16_t			i;
combination* 		r_comb;

r_comb = malloc(sizeof(combination));
r_comb->index = malloc((weight+2)*sizeof(int));

for(i = 0; i < weight; i++) 		r_comb->index[i] = i;

r_comb->index[weight] = length;
r_comb->index[weight+1] = 0;

r_comb->length = length;
r_comb->weight = weight;

return r_comb;

}

inline int next_comb(combination* a_comb) {

uint16_t			k = 0;

while(a_comb->index[k]+1 == a_comb->index[k+1]) {
a_comb->index[k] = k;
k++;
}

a_comb->index[k]++;

if (k < a_comb->weight)
return TRUE;

return FALSE;

}

void free_comb(combination* a_comb) {

free(a_comb->index);
free(a_comb);

}
```

We then call it:

```combination*		comb;

comb = new_comb(HEIGHT, WEIGHT);

do {

[...]

} while(next_comb(comb));
```

Got a better implementation? Submit it in the comments!