0

This is based on a question from the Algorithms book by Cormen et al. They provide an algorithm for randomly permuting an array. It goes some thing like (page 93 of http://www.mif.vu.lt/~valdas/ALGORITMAI/LITERATURA/Cormen/Cormen.pdf)- 

RANDOMIZE-IN-PLACE(A)
1 n = A.length
2 for i = 1 to n
3 swap A[i] with A[RANDOM(i, n)]

They then prove that this produces all permutations with equal probability. In the exercises, they ask what would happen if they replaced line 3 with A[RANDOM(1,n)]. Would all permutations still be equally likely? Im guessing not since the loop invariant is no longer satisfied. But which permutations are more likely in this new algorithm?

Rohit Pandey
  • 2,443
  • 7
  • 31
  • 54
  • This would not be a duplicate question if you asked for a _proof_ that permutations aren't equiprobable. The given link doesn't prove anything. – Gene Jan 01 '15 at 01:11
  • Actually, the third answer by Eelvex provides a very elegant proof modelling the naïve sort as a Markov chain and using transition matrices. I even proved that the Knuth, Fischer, Yates algorithm does lead us to a uniform distribution across all permutations using that approach. – Rohit Pandey Jan 01 '15 at 10:39

0 Answers0