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