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!