PRICES GO UP AT THE GATE
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! 



Banned

what



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 = =




You are a genius. *pats head*
Spoiler Alert! Click to show or hide 

Stop blaming others for your issues. Stop blaming others for your issues.




People don't seem to enjoy talking to me.


I'm not sure why people want a bunch of shutins to do their homework lately.
http://www.site.uottawa.ca/~lucia/courses/516510/UniPermAppTheory.pdf http://stackoverflow.com/questions/39814483/howtofindthenthbinarypermutation 

Pure, salty evil.  次模試と持ち味め


That second link is my post = =, he didn't tell me how to solve the middle bits




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. 

Larry Ellison is a lawnmower.


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. 



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 



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*(a1) / 2 <= n For k=3, a*(a1)*(a2) / 6 <= n etc. Therefore, if you can solve kth 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 zerobased n to make the math a little more straightforward. 



AHhh, yes of course!!!!




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*(a1) / 2 <= n For k=3, a*(a1)*(a2) / 6 <= n etc. Therefore, if you can solve kth 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 zerobased 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 



Right hmm, the sign should be less than, good job getting it




I mean the ranking start from 0, everything else remains


