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!

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s