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!
Advertisements
