My Math Forum > Math How to find the nth binary permutation?

 Math General Math Forum - For general math related discussion and news

 January 15th, 2017, 10: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!)(4-2)!) = 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, 03:01 PM #2 Global Moderator   Joined: May 2007 Posts: 6,214 Thanks: 492 How is the order of the permutation terms defined?
 January 16th, 2017, 08:01 PM #3 Senior Member   Joined: Aug 2012 Posts: 1,153 Thanks: 252 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 non-Abelian 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 one-line 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 four-element 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 08:04 PM.
 January 16th, 2017, 08:32 PM #4 Senior Member     Joined: Sep 2015 From: CA Posts: 1,109 Thanks: 580 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 08:43 PM.

 Tags binary, binary conversion, find, nth, permutation

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post AshBox Math 1 January 11th, 2017 11:19 AM Antek Probability and Statistics 1 October 2nd, 2015 05:32 PM ungeheuer Algebra 3 October 26th, 2013 08:33 AM rayman Abstract Algebra 5 January 29th, 2012 02:26 AM finalight Applied Math 13 October 14th, 2011 09:16 AM

 Contact - Home - Forums - Top