Let $a$ and $b$ be integers, and let $\text{RANDOM}(a,b)$ be a method returning an integer from the range $[a,b]$ uniformly at random. Now consider the following program, that takes as input an array $A$ of integers.
PERMUTE-BY-SORTING(A)
1. n = A.length
2. let P[1..n] be a new array
3. for i = 1 to n
4. P[i] = RANDOM(1, n^3)
5. sort A, using P as sort keys
I'm solving the problem 5.3-6 in CLRS, which is asking me to explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. In other words, the algorithm should produce a uniform random permutation, even if two or more priorities are identical.
Because priorities are repeated in $P$, we will not get a uniform random permutation. I thought of adding i
to step 4 but that doesn't produce the uniform random permutation. More specifically, the problem is that if two or more priorities are identical we will not get a uniform random permutation since the probability is not same for all the numbers. Ex 1,2,2,3 the probability of 2 in the example is 1/2 and the probability of 1 is 1/4 and 3 is 3/4.