## Convert integer to permutation number

I have no idea how to achieve this, any help would be greatly appreciated and very useful to me.

I have a loop in some computer code, that loops through every single combination of 7 on bits in a 64 bit integer.

For example,

Permutation 1:  00...001111111
Permutation 2:  00...010111111
Permutation 3:  00...011011111


etc.

These evaluate to the decimal numbers:

Permutation 1:  00...001111111 = 127
Permutation 2:  00...010111111 = 191
Permutation 3:  00...011011111 = 223


In total there are:

621,216,192


Combinations (64 choose 7).

Given any decimal/binary number (it doesn't matter which type), that is guaranteed to be a valid permutation value (we don't need to worry about 128 being passed in for example), how can I calculate which permutation number this is?

IE:

whatPermutation(127) = 1;
whatPermutation(191) = 2;
whatPermutation(223) = 3;


etc.

Any help would be brilliant, again, I have no idea where to start.

-

Suppose that your 64 bit number is $n=a_{63} a_{62} ... a_0$. Let $i_7>i_6>\cdots>i_1$ be those indices $j$ for which $a_j=1$. Then $$whatPermutation(n)=1+{i_7\choose 7} +{i_6\choose 6}+\cdots+{i_1\choose 1}.$$ For instance, if $n= 00\cdots 110001011011$, then $$whatPermutation(n)= 1+{11\choose 7}+{10\choose 6}+{6\choose 5}+{4\choose 4}+{3\choose 3}+ {1\choose 2}+{0\choose 1}$$ $$= 549.$$

-
 Bang on! Thanks! – Tom Oct 16 2010 at 0:19 Just as a quick question as well, are there any other constant time complexity solutions, or do you know for sure if this is the only solution? If there is another solution it would be great to know as it may perform better in my evaluations (I'm running billions). – Tom Oct 16 2010 at 0:20

There are 63 choose 7 combinations that start with a 0 and 63 choose 6 that start with a 1. So if you have a 1 in the first bit you are at least 63 choose 7 into the list. Go through the bits in order adding up how many combinations are earlier in the list. So a 1 in the first position adds 63 choose 7. If the first bit is in the second position count 62 choose 7. If the first two bits are 1's count 63 choose 7 + 62 choose 6. You'll need to add 1 for your indexing. Hope this helps.

-
 Ah thanks, that's what I was after, I'll give it a go. Are there any other techniques you know of as well? – Tom Oct 16 2010 at 0:00

The magic words here are that you want to "rank" the k-subsets of $[n]$. See Herb Wilf's lecture notes "East Side, West Side", pp. 18-19. I think this is also in Volume 4, Fascicle 3 of Knuth, The art of computer programming -- at least that's what the titles at Knuth's web page lead me to believe.

-

This correspondence is known as "combinadics", for which there is a nice Wikipedia article. Factoradics is a similar correspondence for permutations.

I'd used similar self-generated methods a few times to compress data structures (thinking of the factoradic method as a "variable radix"), before recently discovering their names. They should probably be better publicized!

-