Is there such a beast as a "perfect" shuffle? :)

[Terry Reedy]

"Christos Georgiou" <DLNXPEGFQVEB at spammotel.com> wrote in message

What you are asking for is not a 'perfect shuffle' but a 'perfectly
random shuffle' -- one that selects from the n! (52! here) possible
with equal probability.

> I needed a function that, given a sequence and a number, would
produce
> the <number>th permutation of the sequence.

The permutations of [0, ..., n-1] or [1, ..., n] can be sorted
(lexicographically ordered) so that they have a 1-1 relation with the
numbers 0 to n!-1.  Kreher and Stinson, Combinatorial Algorithms (for
instance) give enumerate (generate in order), rank(perm->number) and
unrank (number->perm) algorithms (pp.52-6).  [Both sentences are also
true for many other combinatorial sets.]  My Python translation (with
j! calculated incrementally):

def permlexunrank(n, rank):
  '''1<= n is number of items permuted
     !! max n is 12 unless change to longs or Python with conversion
on overflow!!
     0 <= rank <= n!-1
     input not currently tested for validity

     output is corresponding permutation of 1,2,...n
  '''
  perm = [1] * (n+1) # algorithm uses 1-based arrays
  jfac, jfac1 = 1, 1 # 0!, 1!
  for j in range(1,n):
    jfac, jfac1 = jfac1, jfac1*(j+1) # j!, (j+1)!
    d = (rank % jfac1) / jfac
    rank = rank - d * jfac
    perm[n-j] = d+1
    for i in range(n-j+1, n+1):
      if perm[i] > d: perm[i] = perm[i]+1
  return perm[1:] # clip unused 0th element

>>> permlexunrank(1,0)
[1]
>>> permlexunrank(4,0)
[1, 2, 3, 4]
>>> permlexunrank(4,10)
[2, 4, 1, 3]
>>> permlexunrank(4,11)
[2, 4, 3, 1]
>>> permlexunrank(4,12)
[3, 1, 2, 4]
>>> permlexunrank(4,23)
[4, 3, 2, 1]

> Basically, this was because I was aiming for a "perfect" shuffle of
a
> deck of 52 cards, so I wanted to reduce the "randomness" factor to
only
> one number.

The problem is the difficulty in getting a random count in the
appropriate large range.

> My thoughts are that, if I can build a large enough number,  a la:
>
> (random.randint(0, sys.maxint)*(sys.maxint+1) + \
>   random.randint(0, sys.maxint)
> )*(sys.maxint+1) etc...
>
> which optimistically would max beyond n! (perhaps (n+2)!), the
number
> would be a good candidate for a "truly" random shuffle, since the
> function actually uses the (index mod n!) permutation.

If successive randints are psueudorandom -- generated
deterministically from an initial internal seed or set of seeds --
then the number of possible shuffles selected from is at most the
number of possible seeds (or seed sets).  For any algorithm I have
seen, this is less than 52! (> 10**52).  So many or most possible
shuffles have 0.0 probability of being chosen instead of 1/52!.  The
problem is not generating a large number (easy) but chosing from 52!
possibilities (hard).

The standard shuffle method that uses 51 psuedorandom ints to
successively chose cards has same problem.  The number of possible
shuffles is limited by the set of possible seeds.  This is why many
*nix systems come with entropy collecters to store hoped-to-be
uncorreleted random bits from physical events with random aspects (key
presses, internet responses, etc).

Terry J. Reedy