Enumeration of Combinations
C(m,n) gives the number of combinations of m things taken n at a time,
or how many m bit numbers have exactly n bits set, computed by m! /
((m-n)! * n!).
I already know how to iteratively enumerate all combinations one by
one in lexigraphical order.
(http://www.caam.rice.edu/~dougm/twiddle/EnumComb.html)
What I need is to generate any given element given the index, and the
inverse to return the index given the combination.
Both algorithms need to be at worst O(m), or take m or less iterations.
I have already solved this for C(m, 2), but cannot extract a
generalized algorithm for C(m, n).
Solution for C(m, 2):
If bits Y and X are set,
I = (Y*Y - Y)/2 + X
If you know the index I,
Y = 1 + ((sqrt(1 + 8*I) - 1) / 2)
and using the above equation solving for x
X = I - (Y*Y - Y)/2
Set bits X and Y
for example, the 8th element (zero based!) in the C(7, 2) set would be 00010100.
for example, the 0th element will be 0000011.
It is not required that the combinations be listed in any particular
order, as long as the inverse function properly returns the original
index. |
