Permutations to scalars and back again.

[Peter Fairbrother]

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?

Whether 18 ones and 18 zeros arranged together is a permutation is a bit 
problematic, and a question I won't go into - but much more relevant, it 
is a combination.


If you look up elementary combination theory, aka combinatorics, eg on 
google or wikipedia or an elementary statistics book. you will soon find 
a quantity usually represented by nCr “n choose r”

This is the number of ways of selecting r items from n possibilities, 
without replacement, when the order of selection is irrelevant.

This is pretty exactly what the arrangements of 18 ones and 18 zeros you 
describe are.

Values for nCr can be computed on some good calculators, or online 
calculators, or can be found using the expression nCr=n!/r!*(n-r)!.

So, there are nCr = 36C18 = 9075135300 different ways of arranging 18 
ones and 18 zeros.



The above is standard math; the next part, converting combinations to 
integers and back by making and using a table, while fairly simple, is 
not in any textbook I know of.


If we list these combinations as if they were binary numbers, in 
numerical order, we will find that some of them have the first, 
highest-value, bit set, and some do not.

Of the combinations which have the highest bit set, the remaining bits 
will have 17 set bits in 35 bit spaces - ie, there will be 35C17 or 
4537567650 possible combinations with the first bit set.

There will be 36C18 - 35C17 combinations where the first bit is not set.

In this case 36C18 - 35C17 = 35C17, and if we number from 0 the 
smallest-value combination where the first bit is set will be the 35C17 
= 4537567650th combination.

By repeating this, you can find the values where the highest set bit is 
bit34...bit18.

And so on.

This is one way to find the values in the table. Pascal's triangle and 
binomial theorem are two more, though at a deeper level they are all 
much the same.


The important bit is that that for the second-highest set bit, and so 
on, the values of lesser combinations caused by that set bit only varies 
according to which-highest bit is set, and the position it is in.

So we can list the positions of the first-highest, second-highest, and 
so on set bits, look up the values in the table, and add then together 
to get the number for a particular combination.




-- Peter Fairbrother


>>
>> 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-20 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.

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