Enumerating Groups - Algorithm

[TomCollins]

Suppose I have 6 items, and I want to choose 3 from them. I want to enumerate them all in some order.

Obviously I can do this by hand very easily:

ABC
ABD
ABE
ABF
ACD
ACE
ACF
ADE
ADF
AEF
BCD
BCE
BCF
BDE
BDF
BEF
CDE
CDF
CEF
DEF

But suppose I wanted to programatically generate the nth combination? Any easy way to do this?

Group(5) = ACD for this enumeration. I don't care what enumeration is used, as long as it is a proper enumeration.

Here is one way, although it seems fairly far from optimal: you can easily assign unique numbers to each group of 3 by writing them as a 6-digit binary number with a checksum of 3. The first digit encodes whether or not A is in the group, second digit whether B is, etc., so ABD=110100, CDF=001101. Given a particular binary number that represents a valid group, it is fairly easy to compute how many smaller binary numbers also represent a valid group.

For example, there are (5 choose 3) elements with no leading 1, (4 choose 2) elements with a leading 1 but second digit 0, and 2 numbers of the form 1100xx. The rank of ABD is thus (5 choose 3) + (4 choose 2) + 2 +1. You want to invert this operation, which is harder but not so bad.

[TomCollins]

Ideally, I want only unique permutations. So I could use that method, but with binary.
ABCDEF
000111 = DEF
001111 = CDEF

I would have to check to see if the binary representation had a different number of 1's than 3.

Yes, that's what I meant by requiring that the checksum is 3. The only valid numbers for you are ones in which the sum of the digits is 3. That is why you have to do a little bit of combinatorics to convert from the binary number to the enumeration.

If the first 1 is in digit x (counting from the right), second 1 in digit y (again counting from the right) and third 1 is in digit z, then I think that the number in the enumeration is (x-1 choose 3) + (y-1 choose 2)+ (z-1)+1

To go backwards, i.e. to figure out which group of 3 corresponds to n in your enumeration, find x such that (x choose 3) >= n > (x-1 choose 3), and put a 1 in digit x (counting from the right). Then find y such that (y choose 2) >= n-(x-1 choose 3) > (y-1 choose 2), and put a 1 in digit y. Find z similarly.

For n=13, (6 choose 3) >= 13 > (5 choose 3), so we put a 1 in the 6th digit from the right, i.e., we include A. (3 choose 2) = 13-(5 choose 3) > (2 choose 2), so we put a 1 in the 3rd digit from the right. (2 choose 1)= 13-(5 choose 3)-(2 choose 2)> (1 choose 1), so we put a 1 in the 2nd digit from the right, giving us the element 100110, or ADE.

[jason_t]

This is famous and well-known. I think you can find it in Concrete Mathematics by Graham, Knuth and the other guy and definitely in V4. of Knuth's Art of Computer Programming.