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



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;


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

	return FALSE;


void free_comb(combination* 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!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s