Reference no: EM131666743

Question: Suppose that you want to generate a random permutation of N distinct items drawn from the range 1, 2, ..., M. (The case M = N, of course, has already been discussed.) Floyd's algorithm does the following. First, it recursively generates a permutation of N - 1 distinct items drawn from the range M - 1. It then generates a random integer in the range 1 to M. If the random integer is not already in the permutation we add it; otherwise, we add M.

a. Prove that this algorithm does not add duplicates.

b. Prove that each permutation is equally likely.

c. Give a recursive implementation of the algorithm.

d. Give an iterative implementation of the algorithm.