
Math General Math Forum  For general math related discussion and news 
 LinkBack  Thread Tools  Display Modes 
January 15th, 2017, 09:09 PM  #1 
Newbie Joined: Dec 2016 From: United Kingdom Posts: 14 Thanks: 1  How to find the nth binary permutation?
I need to complete this. Let's say I have 4 bits with 2 bits set as 1, 0011. The total number of permutations for this number is 0011, 0101, 0110, 1001, 1010, 1100, 6 cases. This can be computed using the calculation. 4! / ((2!)(42)!) = 6 Now I want to be able to find the nth sequence, for instance 1st number is 0011, second number is 0101. So if I say n=5, I want to be able to get the 5th permutation sequence 1010 from the initial 0011. How do I do this? 
January 16th, 2017, 02:01 PM  #2 
Global Moderator Joined: May 2007 Posts: 6,343 Thanks: 534 
How is the order of the permutation terms defined?

January 16th, 2017, 07:01 PM  #3 
Senior Member Joined: Aug 2012 Posts: 1,572 Thanks: 379 
I just wanted to expand on mathman's point, although he has already given the only possible response to the OP. I wish I had a gift for brevity. I can never write 3 words when 300 will do The question is, how shall we order permutations? As an example, considerthe set of permutations on three objects. We call this set of permutations $S_3$, the symmetric group on three letters. https://en.wikipedia.org/wiki/Symmetric_group Also this is a good article. https://en.wikipedia.org/wiki/Permutation As you can see from the Wiki link, mathematicians have given a lot of thought to this set and its close relatives $S_n$ as $n$ varies over the positive integers. $S_3$ is the simplest example of a nonAbelian group, so it's a great source of examples and visualizations. We can notate a permutation like this: $ \left( \begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix} \right) $ This is the permutation that sends $1$ to $3$, sends $3$ to $1$, and leaves $2$ alone. For brevity we can notate this permutation as $\langle 3 2 1\rangle$. I did not use parens because the oneline notation in parens typically implies the cycle notation for permutations, which is different. One sensible way to order these permutations would be in lexicographic order of the second line of the notation. Lexicographic order is just plain old alphabetical order, left to right. In this order, $\langle 3 1 2\rangle$ comes before $\langle 3 2 1\rangle$. But this is just one way to order $S_3$. We could use reverse lexicographic order. Or we could define our own order. How many possible orders are there? If you think of it, an order is just some permutation on the elements of $S_3$. There are $6$ elements of $S_3$ (needs proof) and in general $n!$ elements of $S_n$ (needs proof). Therefore there are $6! = 120$ different ways we could order the set of permutations of a three element set. In your case you have a fourelement set so there are $(4!)!$ possible orderings of the set of permutations on the original set. That's $24!$ which is a big number. Also you mentioned that the elements you're permuting are each in one of two states, so that you have bitstrings like $0011$. In that case, swapping the first and second elements doesn't change the bitstring. I'm afraid I'm not a combinatorialist but you have to account for those cases and divide them out to get the exact number of possible orderings on your set of permutations. In fact I see that you already did this, so you are way ahead of me here. Either way, you have to tell us how you are ordering your permutations. And that's what mathman asked in far fewer words And by the way ... since they're bitstrings, why not just order them as binary numbers? That seems pretty simple. $0011$ comes before $1010$. Can you do that? Last edited by Maschke; January 16th, 2017 at 07:04 PM. 
January 16th, 2017, 07:32 PM  #4 
Senior Member Joined: Sep 2015 From: Southern California, USA Posts: 1,500 Thanks: 757 
as I said when I answered this last time.... if you are really just looking at the groups of 4 bits that have 2 1s in them. There are 4C2 = 6 of them. Arranged in increasing order of value they are 0011 0101 0110 1001 1010 1100 put these into an array and just look up the nth one when you need it. That's not the order you want? Fine. Store them in the array in the order you do want. I'm curious why you've posted an exact duplicate of someone else's question. Last edited by romsek; January 16th, 2017 at 07:43 PM. 

Tags 
binary, binary conversion, find, nth, permutation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Need to get the nth binary permutation.  AshBox  Math  1  January 11th, 2017 10:19 AM 
Find max size of clique in permutation graph  Antek  Probability and Statistics  1  October 2nd, 2015 05:32 PM 
0.1 binary  ungeheuer  Algebra  3  October 26th, 2013 08:33 AM 
find an inverse of a permutation cycle  rayman  Abstract Algebra  5  January 29th, 2012 01:26 AM 
find binary relation  finalight  Applied Math  13  October 14th, 2011 09:16 AM 