ShimPossible

Combination Generation

I ran across a wonderful article a while ago about a Combination / Permutation class that generated them as a stream.  It’s a great idea.  It makes unit testing pretty easy, as you can have the class make sure you hit all your test cases.  Sadly I wasn’t able to find the article again, at least I don’t think i was able to find it.

Anyway, I went a made my own combination generator.  For those wondering what a Combination is, its arranging K items from a set of N items, order doesn’t matter.  So given 5 items, and only taking 3 at a time you would get

0,1,2
0,1,3
0,1,4
0,2,3
0,2,4
0,3,4
1,2,3
1,2,4
1,3,4
2,3,4
The way this works is quite simple.  Each column has a min and max value that it can hold.  The first column goes from 0-2 (or 0 to (N-K) ), the last column goes from N-K to N-1.  You can easily generalize this into column C can hold a value from C to N-K+C.  The value of N-K can be precomputed.  Armed with this knowledge you can now make all your combinations.  First start with the identity (0,1,2,…,n).  To get the next combination, start at the right most item, and move left until you hit the first item that can be incremented, in other wards, the value is between C and N-K+C.  Increment this value, then move back right and set each of these columns equal to 1 more then their left item.

So given 0,3,4,  we start at the right (4).  4 is the max value for this column, so we move left.  3 is also the max value for this column, so we move left again.  0 is between 0 and 2, so we can still increment it.  We change it to 1.  Now the array is 1,3,4.  Next we go back right and add one to each column, so we change the 3 into 1+1, which is 2.  We change the 4 into 2+1, which is 3.  This leaves us with the next combination of 1,2,3.

The last combination has the pattern of the first item equal to N-K (or 2 in our case).  When we reach this case we stop.

Ok, thats my little walk through on combinations. I’ll put something up about permutations next

Filed by shim at December 23rd, 2006 under Uncategorized