Convert integer to permutation number - MathOverflow

Convert integer to permutation number

2010-10-15T23:40:01Z

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 by Ross Millikan for Convert integer to permutation number

2010-10-15T23:49:20Z

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 by Michael Lugo for Convert integer to permutation number

2010-10-15T23:55:34Z

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 by Richard Stanley for Convert integer to permutation number

2010-10-16T00:12:52Z

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 by cxseven for Convert integer to permutation number

2010-10-16T09:50:13Z

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!