5.3-3

Suppose that instead of swapping element A[i] with a random element from the subarray A[i....n] , we swapped it with a random element from anywhere in the array:


PERMUTE-WITH-ALL(A)
1 n = A:length
2 for i = 1 to n
3 swap A[i] with A[1...n]
Does this code produce a uniform random permutation? Why or why not?


The above code will not produce uniform random permutation. The above for loop increments i but the call to random take 1 to n as arguments. So the probability for each no from 1 .. n is fair. This is just like tossing a coin twice where the probability is fair for H an T. The probability is 1/4 for each tossing since you can get (HT,TH,HH,TT) with 1/4 probability which $1/2^2$.
Ex: consider n = 3 A[0] = 1 ,A[2] = 2,A[3] = 3 then the possible no of permutations 3^3 from Random(1,2)(since it is called from PERMUTE-WITH-ALL(A) thrice).
permutations:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Similarly probability of picking a random number from n numbers n times is $1/n^n$. But for a uniform probability distribution according lemma 5.4 it should be $1/n!$ if PERMUTE-WITH-ALL did produce a uniform random permutation, then each permutation would occur 1/6 of the time. That would mean that each permutation would have to occur an integer number m times(bcoz 1/27 is not equal 1/6 so there might be an integer m), where m/27 = 1/6. No integer m satisfies this condition.