Permutations to scalars and back again.
Peter Fairbrother
peter at m-o-o-t.org
Mon Sep 12 07:21:13 PDT 2016
On 12/09/16 11:24, Peter Fairbrother wrote:
> On 12/09/16 02:09, James A. Donald wrote:
>> I need to be able to do two of the following three tasks.
>>
>> Generate a permutation of eighteen ones and eighteen zeros with equal
>> probability for each permutation. Or equivalently shuffle eighteen
>> black cards and eighteen red cards.
>>
>> Sequentially generate all possible permutations with each permutation
>> generated once and only once.
>>
>> Map between permutations and scalars, such that each permutation maps to
>> unique number, and the set of numbers that represents valid permutations
>> is dense.
>>
>> Could someone point me to the relevant literature, or literature for
>> converting between different representations of a permutation?
>>
>> Since there are only two classes of items being shuffled, this class of
>> permutations has a variety of special and convenient properties.
>
> Indeed.
>
> I had a similar problem, the way I solved it was to create tables as
> follows - I had to do a lot of conversions.
>
> We are going to write the permutations as binary numbers, and then
> number them according to size.
>
> Look for the first 1 in the permutation, ie the 1 which is in the
> highest position.
>
> It can be at position 18, and then all the lower bits will be ones so it
> is permutation number 1.
>
> If the first bit is in position 19 then there are 18 possible
> lower-value permutations. These are permutations 2 to 19. The table
> value for a first bit in position 19 is 2.
>
> If the first bit is in position 20 then there are x possible
> permutations, permutations 20 to x. The table value for a first bit in
> position 20 is 20.
>
> And so on, but we have to calculate x first.
>
> Looking at permutations with a first bit in position 19, if the second
> bit is in position 18 then it is worth 1, if it is in position 17 then
> it is worth 0. If the third bit is in position 17, it is worth 1, and so
> on.
>
> Note that eg a fifth bit in position 14, or a 17th bit in position 3, is
> always worth 1, no matter where the other bits are positioned.
>
> This is true (with the appropriate value) for any combination of
> bitnumber and bitposition - it doesn't change if the other bits change
> position.
>
> So we create a table with values for the first, second, third etc bits
> of the permutation, and the positions in the permutation they are found
> in. We total those values, which gives the number of the permutation.
>
> Calculating the permutation from the permutation number is
> straightforward, find possible ranges and subtract.
>
>
>
> Hope this is clear, written in a rush. My email is real, you can contact
> me offlist.
>
> -- Peter Fairbrother
Here's an example table for 3 ones and 3 zeros.
The entries are written as x,y[v], where x is 1 for the first 1, and so
on, y is the position of the xth 1 in the permutation, v is the table
value. The number of the permutation is found by adding three values for
x=1,2,3 together.
position
123456
permutation
| permutation number
| first 1
| second 1
| third 1
|
000111 - 0 - 1,4[0] + 2,5[0] + 3,6[0]
001011 - 1 - 1,3[1] + 2,5[0] + 3,6[0]
001101 - 2 - 1,3[1] + 2,4[1] + 3,6[0]
001110 - 3 - 1,3[1] + 2,4[1] + 3,5[1]
010011 - 4 - 1,2[4] + 2,5[0] + 3,6[0]
010101 - 5 - 1,2[4] + 2,4[1] + 3,6[0]
010110 - 6 - 1,2[4] + 2,4[1] + 3,5[1]
011001 - 7 - 1,2[4] + 2,3[3] + 3,6[0]
011010 - 8 - 1,2[4] + 2,3[3] + 3,5[1]
011100 - 9 - 1,2[4] + 2,3[3] + 3,4[2]
100011 - 10 - 1,1[10] + 2,5[0] + 3,6[0]
100101 - 11 - 1,1[10] + 2,4[1] + 3,6[0]
100110 - 12 - 1,1[10] + 2,4[1] + 3,5[1]
101001 - 13 - 1,1[10] + 2,3[3] + 3,6[0]
101010 - 14 - 1,1[10] + 2,3[3] + 3,5[1]
101100 - 15 - 1,1[10] + 2,3[3] + 3,4[2]
110001 - 16 - 1,1[10] + 2,2[6] + 3,6[0]
110010 - 17 - 1,1[10] + 2,2[6] + 3,5[1]
110100 - 18 - 1,1[10] + 2,2[6] + 3,4[2]
111000 - 19 - 1,1[10] + 2,2[6] + 3,3[3]
: 1 2 3
1: 10 x x
2: 4 6 x
3: 1 3 3
4: 0 1 2
5: x 0 1
6: x x 0
You will note that the numbers are the sum of the number beneath and the
number beneath and to the right. This makes calculating tables (or
individual values) easy.
-- Peter Fairbrother
More information about the cypherpunks
mailing list