🚀 go-pugleaf

Stephen Bloch (sbloch@silver.cs.umanitoba.ca) wrote:
: sumner@math.scarolina.edu (David Sumner) writes:
: >> In an earlier post I wrote that an easy way to generate a
: >> random permutation of the integers 1-n was:
: >> >      ++++++++++++++
: >> >  Initialize  A[n] as the array [1, 2, 3, 4,..., n]
: >> >        for i=1 to n
: >> >        z = random(n)
: >> >        t = a[i]
: >> >        a[i] = a[z]
: >> >        a[z] = t
: >> >        next i
: >> >    ++++++++++++++
: >> There is a typo in this. The line 'z = random(n)' should
: >> be 'z = random(i)'

: I THINK (but am not sure) the
: corrected one is also incorrect, for the reasons Thomas states.

The corrected algorithm can be seen to be correct by a simple
inductive argument.  Namely, after the i-th iteration, A[1]...A[i]
contains a random permutation of 1,...,i, and A[i+1]...A[n] contains
the numbers (i+1),...,n in sequence.  The next iteration swaps A[i+1]
= (i+1) with a randomly-chosen A[z], where 1 <= z <= i+1.  Thus, (i+1)
is equally likely to go into any of the first i+1 slots, and the
remaining positions end up being filled with a random permutation of
1,...,i.  This results in a random permutation of 1,...,i+1 as
desired.

Since the induction hypothesis is obviously true for i=0, it holds for
all i<=n by induction.  Thus, after the last iteration, A[1],...,A[n]
contains a random permutation of 1,...,n.

==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================