My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Math (http://mymathforum.com/math/)
-   -   How to find the nth binary permutation? (http://mymathforum.com/math/338608-how-find-nth-binary-permutation.html)

SophiaRivera007 January 15th, 2017 09:09 PM

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?

mathman January 16th, 2017 02:01 PM

How is the order of the permutation terms defined?

Maschke January 16th, 2017 07:01 PM

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?

romsek January 16th, 2017 07:32 PM

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.


All times are GMT -8. The time now is 08:39 PM.

Copyright © 2019 My Math Forum. All rights reserved.