Randomize a List problem

[David Hayden]

Coming back to this after rediscovering One Minute Marvels.

The original algorithm is basically this:

Code:

T = size of list
For n = 1 to t
    R = random number from 1 to n
    Rotate the last R items of the list to the right

Consider the first item in the list. The only time it can move is on the last loop iteration when n=t, and even then, only when R=t, which has probability 1/t Also, since the algo rotates the list, the first item can only move to position 2.

Similarly, the second item can only move during the last or second-to-last iteration. It can move to position 3 or 4.

And so on down the line. Here’s a table showing where the items can move to for a 9-item list. Each row represents the starting position of an item and each colunm is a possible ending positions:

Code:

     1 2 3 4 5 6 7 8 9
1    * *
2      * * *
3        * * * *
4          * * * * *
5    *       * * * * *
6    * * *     * * * *
7    * * * * *   * * *
8    * * * * * * * * *
9    * * * * * * * * *

Only items 8 and 9 can land in all positions.