First  Prev  1  2  3  Next  Last
Post Reply nth binary permutation for any binary numbers
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/3/16
I want to get the nth binary permutation for any binary numbers. For instance, for 00111, where 3 bits are set to 1. It has 10 cases:

00111 1
01011 2
01101 3
01110 4
10011 5
10101 6
10110 7
11001 8
11010 9
11100 10

If I want to get the binary bit associated with the rank number, how can I do it(rank number 8 = 11001)? Or if I want to get the rank number from the binary bit, how can I do it(11010 = rank number 9)?

Xero essential told me that I can get the most significant bit from the rank number like this a*(a+1)/2 >= n, where a represents the most significant bit. So for rank number n=9, I would have a*(a+1)/2 >= 9 where a is 4 and above and start from 0, so the most significant bit is 1 counting from 43210. The link to the post is here. However he did not tell me how to solve for the rest of the bits. So I would like to know how to solve for the rest all the way to least significant bit. If there is also a more efficient way to solve this let me know as well. Thanks!
19010 cr points
Send Message: Send PM GB Post
22 / F
Offline
Posted 10/3/16 , edited 10/5/16
what
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/3/16 , edited 10/3/16
I dunno if I'm not smart for not being able to solve this or I am smart for being able to come up with this = =
19625 cr points
Send Message: Send PM GB Post
18 / F / Croatia
Offline
Posted 10/3/16
You are a genius. *pats head*

Posted 10/3/16
11224 cr points
Send Message: Send PM GB Post
Offline
Posted 10/3/16 , edited 10/4/16
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/3/16
That second link is my post = =, he didn't tell me how to solve the middle bits
1170 cr points
Send Message: Send PM GB Post
16 / M
Offline
Posted 10/3/16

fredreload wrote:

I want to get the nth binary permutation for any binary numbers. For instance, for 00111, where 3 bits are set to 1. It has 10 cases:

00111 1
01011 2
01101 3
01110 4
10011 5
10101 6
10110 7
11001 8
11010 9
11100 10

If I want to get the binary bit associated with the rank number, how can I do it(rank number 8 = 11001)? Or if I want to get the rank number from the binary bit, how can I do it(11010 = rank number 9)?

Xero essential told me that I can get the most significant bit from the rank number like this a*(a+1)/2 >= n, where a represents the most significant bit. So for rank number n=9, I would have a*(a+1)/2 >= 9 where a is 4 and above and start from 0, so the most significant bit is 1 counting from 43210. The link to the post is here. However he did not tell me how to solve for the rest of the bits. So I would like to know how to solve for the rest all the way to least significant bit. If there is also a more efficient way to solve this let me know as well. Thanks!


Congratulations, you have fucked my brain.
61245 cr points
Send Message: Send PM GB Post
28 / M
Offline
Posted 10/3/16 , edited 10/3/16
Do it recursively. Using your example...

n = 9 (rank of the permutation)
k = 3 (number of bits that are on)
a * (a + 1) / 2 >= 9 yields a = 4

n = n - a = 5
k = k - 1 = 2
a * (a + 1) / 2 >= 5 yields a = 3

n = n - a = 2
k = k - 1 = 1
a * (a + 1) / 2 >= 2 yields a = 1

n = n - a = 1
k = k - 1 = 0 (stop recursion at k=0)

So your bits are 4, 3, and 1.

EDIT: Not quite. I forgot to divide by 2 in the bold equation. However, "10" is the second permutation for k=1 so maybe the a*(a+1)/2>=n is not valid for k=1.
Posted 10/3/16 , edited 10/3/16
unsigned int curPerm = 7;
unsigned int nextPerm = 0;
unsigned int t = 0;
int rank = 9;


for(int i =0 ; i < rank -1 ; i++)
{


t = (curPerm | (curPerm - 1)) + 1;
nextPerm = t | (((( t & -t) / (curPerm & -curPerm)) >>1) -1);


curPerm = nextPerm;


}

cout << nextPerm << endl;


You could easily do it recursively but I am lazy. Set curPerm to a number with the number of 1 bits you want and it will compute the permutation from that point on. If you don't mind an iterative solution
61245 cr points
Send Message: Send PM GB Post
28 / M
Offline
Posted 10/3/16 , edited 10/5/16
I believe I figured it out. The relationship between a, k, and n is given by the following equation.



For k=1, a <= n
For k=2, a*(a-1) / 2 <= n
For k=3, a*(a-1)*(a-2) / 6 <= n
etc.

Therefore, if you can solve k-th order polynomials to get the position of the most significant bit, then you can solve this recursively using the method I showed in my previous post.

EDIT: I forgot to mention that I zero-based n to make the math a little more straightforward.
Posted 10/4/16
AHhh, yes of course!!!!
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/4/16

staphen wrote:

I believe I figured it out. The relationship between a, k, and n is given by the following equation.



For k=1, a <= n
For k=2, a*(a-1) / 2 <= n
For k=3, a*(a-1)*(a-2) / 6 <= n
etc.

Therefore, if you can solve k-th order polynomials to get the position of the most significant bit, then you can solve this recursively using the method I showed in my previous post.

EDIT: I forgot to mention that I zero-based n to make the math a little more straightforward.


So k is factorial based? Thanks for the help btw, I wonder how he came up with the initial algorithm (a)*(a+1)/2
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/4/16
Right hmm, the sign should be less than, good job getting it
3390 cr points
Send Message: Send PM GB Post
30 / M
Online
Posted 10/4/16
I mean the ranking start from 0, everything else remains
First  Prev  1  2  3  Next  Last
You must be logged in to post.