Generating Combinations

[solver]

I usually generate combinations using this method:

If I have to generate combinations of k out of n elements, I loop from 0 to 2^n-1 and count the number of 1s in each iteration's bin. representation. If the number of 1s=k, I pick it and the positions with 1s are considered IN and others OUT. This forms one case of combinations.

e.g. To pick 3 elements out of 4

loop from 0000 to 1111, and pick
0111 (B, C, D are in)
1110 (A, B, C are in)
1101 (A,B, D are in)
1011 (A, C, D are in)


Is there any quicker/shorter piece of code that you employ?

[zorbathut]

I'm a big fan of recursion.

I'll just implement it in almost-psuedocode, I'm lazy :P

[cpp]int totalitemcount; // initialized to however many items there are
bool taken[ totalitemcount ]; // initialized to all false, needs to be >= totalitemcount
int wanteditems; // however many items the person wants
int items[ wanteditems ]; // doesn't have to be initialized, needs to be >= wanteditems
void doit( int pos, int got ) {
if( got == wanteditems ) {
// use taken[ 0 ] through taken[ wanteditems - 1 ] here, in whatever it was you wanted to do with them :P
} else if( totalitemcount - pos >= wanteditems - got ) {
taken[ pos ] = true;
items[ got ] = pos;
doit( pos + 1, got + 1 );
taken[ pos ] = false;
doit( pos + 1, got );
}
}[/cpp]

and for your example . . .
[cpp]totalitemcount = 4;
wanteditems = 3;
memset( taken, 0, sizeof( taken ) ); // yes, the taken array could be 4 long, and the items array could be 3 long
doit( 0, 0 );[/cpp]

and that's it.

Obviously I have arrays with nonconstant lengths, and you can make them constant or dynamically allocate them, your call.

[solver]

Obviously I have arrays with nonconstant lengths, and you can make them constant or dynamically allocate them, your call.

Thanks for your reply.

How about using std::map<int,bool> taken; instead of bool taken[ totalitemcount ]; ? (not sure if thats an overkill ... or may even hurt performance when I'm dealing with large "totalitemcount")

[zorbathut]

Not really any point IMHO - since the input is integers [0,n), the straight array will be more efficient. If you want to use something dynamically sized to keep from out-of-boundsness (which is a really good idea *grin*), I recommend vector< bool >. Performance *probably* wouldn't be a problem with map, but, well, why bother? It's ickier. :)

You might also consider writing a "predoit" function that initializes the vector, sets the globals, and calls the main function with 0,0 . . . might make it a bit easier. Might not. :)

[solver]

Thanks.

[Stefan Pochmann]

I've written a tutorial on this topic a while ago that also includes several algorithms:

http://www.cs.ubc.ca/~pochmann/topcoder ... index.html