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! 



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 





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


