|January 15th, 2017, 10:09 PM||#1|
Joined: Dec 2016
From: United Kingdom
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, 08:01 PM||#3|
Joined: Aug 2012
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.
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:
1 & 2 & 3 \\
3 & 2 & 1
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|
Joined: Sep 2015
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
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.
|binary, binary conversion, find, nth, permutation|
|Thread||Thread Starter||Forum||Replies||Last Post|
|Need to get the nth binary permutation.||AshBox||Math||1||January 11th, 2017 11: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 02:26 AM|
|find binary relation||finalight||Applied Math||13||October 14th, 2011 09:16 AM|