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