Convert integer to permutation number

Question

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.

Answer 1

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. $$

Answer 2

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.

Answer 3

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!

Answer 4

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.

Answer 5

Take the Binary value as an eight bit string. The number of Rotate left operations it takes to get the left most bit as zero is the permutation number( starting from 0)

This is the shortest way to get the permutation number.

Let me explain

if the no is.......................11011111

Rotate left #1     10111111          MSB   1 so repeat
Rotate left #2     01111111          MSB   0 so terminate and 
permutation no = #2 with startpoint 0  or 2+1=3 with startpoint 1(as is your scheme)

Hope that takes care of the downvote

Alternatively

do a bit wise not operation on the byte

So not(11011111 ) -> 00100000 = M; L= Log2(M) ; permutation no = 7-L with startpoint 0 or 7-L+1 with startpoint 1(as is your scheme)

Formula: whatPermutation(n)= 8-LogBase2(Bitwise_not(n)) where n is as described by you

Example: whatPermutation("191") = whatPermutation(10111111)=
8- LogBase2(Bitwise_not(10111111)) = 8 -LogBase2(01000000)= 8-6 = 2

Time complexity : All I can comment is that this would take three x86 instructions Does this help?