Generating all combinations of n elements taken t at a time

I don’t usually share the code I write for my research projects, unless someone asks for it. Anyway, today I had fun writing some C code, and I think it may turn out to be useful for other people. It’s written almost well enough to be acceptable, so here you are.

I implemented Chase’s sequence algorithm to generate the bit-strings corresponding to each combination of n elements taken t at a time. The algorithm is described in Donald E. Knuth’s “The Art Of Computer Programming”, Vol. 4, Fasc. 3, page 13. I implemented it in C and added very few comments, so refer to TAOCP if you have any doubts.

The code is distributed under the BSD 2-clauses License.

Download chaseseqcombgen.c

Comments 2

  1. Marcus Reid wrote:

    Can you give an example of its use?

    Posted 09 Mar 2012 at 16:18
  2. Matteo wrote:

    Sure. You call it as “./chaseseqcombgen n t” and it will print to stdout the bitstrings (i.e. strings of zeroes and ones) corresponding to the combinations of n elements taken t at a time. Each printed line corresponds to a combination. Each combination is a string of n characters, of which t are ones, and n-t are zeroes. A “1” in position i (0 less or equal than i less or equal than n-1) means that element “i” (in some predefined order of the elements) appears in the combination. A “0” means that the element does not.

    I personally use it as a key-generating step in a Hadoop MapReduce algorithm. I need to create all combinations of n items and associate a unique key to each combination. This does the job of creating the unique key and at the same time telling me exactly which items belong to the combination.

    I believe it can be useful if you modify the code so that, instead of printing the combination bitstring, you do something with the combination, e.g., it’s a good place to actually build the combination.

    Posted 09 Mar 2012 at 18:56

Post a Comment

Your email is never published nor shared. Required fields are marked *