Chapter 7, Problem 36SE

The following method can be used to generate a random permutation of a sequence of n terms. First, interchange the nth term and the r(n)th term where r(n) is a randomly selected integer with 1< r(n)< n. Next, interchange the (n - i)st term of the resulting sequence with its r(n - i)st term where r(n -1) is a randomly selected integer with 1< r(n -1)< n -1, Continue this process until j - n. where at the jth step you interchange the (n - j+i)st term of the resulting sequence with its r(n - j+i)st term, where r(n - j+1) is a randomly selected integer with 1< rfn - j -1)< n - j+1. Show that when this method is followed, each of the n! different permutations of the terms of the sequence is equally likely to be generated. [Hint: Use mathematical induction, assuming that the probability that each of the permutations of n -1 terms produced by this procedure for a sequence of n -1 terms is i/(n -1)!.]