View Single Post
  #2  
Old 12-01-2005, 06:41 PM
Guest
 
Posts: n/a
Default Re: Enumerating Groups - Algorithm

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.
Reply With Quote