My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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


Reply
 
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!)(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?
SophiaRivera007 is offline  
 
January 16th, 2017, 02:01 PM   #2
Global Moderator
 
Joined: May 2007

Posts: 6,275
Thanks: 516

How is the order of the permutation terms defined?
mathman is offline  
January 16th, 2017, 07:01 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,428
Thanks: 352

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 07:04 PM.
Maschke is offline  
January 16th, 2017, 07:32 PM   #4
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: CA

Posts: 1,296
Thanks: 664

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.
romsek is offline  
Reply

  My Math Forum > Math Forums > Math

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





Copyright © 2017 My Math Forum. All rights reserved.