PERMUTE-BY-SORTING with similar priorities

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.

• I think some context is missing here. What is the contents of $A$? How does PERMUTE-BY-SORTING work? What goes wrong if the priorities are not distinct? Please put more effort into the question. – Yuval Filmus Jun 9 '13 at 2:18
• Contents of A are not needed in the question because we are trying randomize the array A by generating priorities. We are not performing any operation other than doing permutation based on priorities created. – gopal Jun 9 '13 at 3:34
• Sorry, I still don't understand the question, and in particular what the current algorithm is doing and why it breaks when priorities are repeated. Voting to close. – Yuval Filmus Jun 9 '13 at 5:15
• @YuvalFilmus if you read this "That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical" you should understand. It states that needs uniform random permutation. If you have a priority repeated we will not get a uniform permutation since it will have a better chance than the rest of the priorities. Can you re open the question now ? – gopal Jun 9 '13 at 19:18
• @Dukeling Sure, with $a$ and $b$ probably included. My points is that there's no reason for anyone to guess. It's up to the OP to make his/her question clear, and I'm encouraging him/her to show respect and get more/better answers by being clear, concise and by showing effort. In fact, I remember being asked this precise question in an undergrad exam. – Juho Jun 9 '13 at 19:40

The easiest way is to generate a random permutation in $P$. Here is pseudocode:

1. Initialize $P$ with $P[i] = i$ for $i = 1,\ldots,n$.
2. Repeat for $i = 1,\ldots,n-1$:
1. Let $j$ be a random number in the range $i,\ldots,n$.
2. Swap $P[i]$ and $P[j]$.

If our initial array is A = <1, 2, 3, 4> and we choose random priorities P = <36, 3, 97, 19>, we would produce an array B = <2, 4, 1, 3>

Now if random priority array P= <36,3,3,19> and now we use elements of P to sort array A, using say merge sort, our resulting array B would be <2,3,4,1>. As we saw, all the elements are still equally likely to be produced.

• The resulting permutation can't be uniformly distributed, as $(n^3)^n$ is not a multiple of $n!$. – D.W. Jul 3 '13 at 7:17
• @Yuval: Your answer to generate random permutation is somewhat same to another method 'RANDOMIZE-IN-PLACE' for randomized algorithms. As specified in the ques, we need a measure for Permute by sorting method. We can't change the method of randomization i.e. P[i] = RANDOM(1, n^3) – Tanu Saxena Jul 3 '13 at 10:15

A way to do is this:

PERMUTE-BY-SORTING-2(A)
1. n=A.length
2. Let P be an array [1 .. n^3]
3. Initialize P with P[i]=i for i=1,...,n^3.
4. For i=1,…,n:
5.     Let j be a random number in the range i,…,n^3.
6.     Swap P[i] and P[j].
7. sort A[1..n], using P[1..n] as sort keys

However this only produces unique priorities in P[1..n]. Thus avoiding rather than handing the case where P[1..n] has non-unique numbers.

• Your loop will never change P[1..n], after $i$ is bigger than $n$. Still you run it up to $n^3$. Why? Also your algorithm is $\Theta(n^3)$ in time and space for the initialization alone, which is very inefficient for the problem at hand. – FrankW Sep 28 '14 at 12:00
• Agreed, I stand corrected. It is sufficient for the for loop in line 4 to run from 1..n. So, edited the algorithm. – Narayan Ramamurthi Sep 28 '14 at 12:05
• Also, the original PERMUTE-BY-SORTING itself is very inefficient and inaccurate [in that it produces uniform random permutation at a probablity of at least (1-1/n) only, which is not same as a probablity of 1]. – Narayan Ramamurthi Sep 28 '14 at 12:14
• The original algorithm runs in time $O(n\log n)$; yours runs in time $O(n^3)$. That's a huge difference: imagine trying to permute a list of a million elements, for example. Also, it's not at all obvious that your algorithm produces all permutations with equal probability: this needs to be proven. – David Richerby Sep 28 '14 at 12:57
• In that case, can we get a better answer than Yuval Filmus? (Given the below note from Tanu Saxena saying "our answer to generate random permutation is somewhat same to another method 'RANDOMIZE-IN-PLACE' for randomized algorithms. As specified in the ques, we need a measure for Permute by sorting method. We can't change the method of randomization i.e. P[i] = RANDOM(1, n^3) ") – Narayan Ramamurthi Sep 28 '14 at 13:27