5.3-6

5.3-6 Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.

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$)+ i
5 sortA, using P as sort keys
I made simple change. I am adding i in step 4.I changed the original algorithm form P[i] = RANDOM(1, $n^3$) to P[i] = RANDOM(1, $n^3$)+i. Lets say we get all equal priorities. But i is distinct it would make each of priorities distinct.

Ex:
n = 3
i =1
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 1
P[1] = 2;


i = 2
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 2
P[1] = 3;


i = 3
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 3
P[1] = 4;
It's a small change but it would create distinct priorities. This doesn't feel right. please check again.Still we can get same priorities when i = 1 and random returns 2 and i = 2 random returns 1.Rework is needed.