6
$\begingroup$

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.

$\endgroup$

5 Answers 5

17
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Tom
    Oct 16, 2010 at 0:20
  • 1
    $\begingroup$ Probably you have already thought of that, but cache your binomial computations. This should yield a considerable saving. $\endgroup$ Jun 9, 2013 at 13:29
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

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

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.