Random shuffle

[WhiteCube]

I was reviewing a sudoku program, which lead me to consider this pseudocode for shuffling 9 elements.

FOR i = 1 TO 9
 r = random, from 1 to 9
 swap element i and r

At first glance it seems fair, but there's bias here.

Let P(s,d) be the probability that an object that starts in position s (source) finishes in position d (destination).

Very easy to estimate with a monte carlo simulation, but I was curious about the exact value.

I tried a pen & paper mathematical approach, but one of the cases that can happen to an object is very tricky to express.

In the end I got an exact answer using an approach similar to counting paths down Pascal's triangle.

In the final results there was a wide range in values and some unexpected symmetry.

P(3,2) = P(8,7)

P(a,9-b) = P(b+1,10-a)

 

[WhiteCube]

P(s,d)

A = array of 9 zeros
A(s) = 1
FOR I = 1 TO 9
  B = A
  A = array of 9 zeros
  FOR S = 1 TO 9
    FOR R = 1 TO 9
      IF S == I
        A(R) += B(S)
      ELSE
        IF S == R
          A(I) += B(S)
        ELSE
          A(S) += B(S)

return A(d) / 9^9

I'm not thrilled with that nested IF.

Single letter variable names are kind of my style inside a function. I'm not saying its good.

 

[WhiteCube]

The diagram I was using to count paths has 180 degree rotational symmetry, so that's where the P(a,b) = P(n-b+1,n-a+1) came from.

Not a fruitful rabbit hole to go down, but that's life.