1
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 9, 2013 at 2:18
  • $\begingroup$ 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. $\endgroup$
    – gopal
    Jun 9, 2013 at 3:34
  • $\begingroup$ 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. $\endgroup$ Jun 9, 2013 at 5:15
  • $\begingroup$ @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 ? $\endgroup$
    – gopal
    Jun 9, 2013 at 19:18
  • 2
    $\begingroup$ @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. $\endgroup$
    – Juho
    Jun 9, 2013 at 19:40

3 Answers 3

5
$\begingroup$

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]$.
$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The resulting permutation can't be uniformly distributed, as $(n^3)^n$ is not a multiple of $n!$. $\endgroup$
    – D.W.
    Jul 3, 2013 at 7:17
  • $\begingroup$ @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) $\endgroup$ Jul 3, 2013 at 10:15
-2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – FrankW
    Sep 28, 2014 at 12:00
  • $\begingroup$ Agreed, I stand corrected. It is sufficient for the for loop in line 4 to run from 1..n. So, edited the algorithm. $\endgroup$ Sep 28, 2014 at 12:05
  • $\begingroup$ 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]. $\endgroup$ Sep 28, 2014 at 12:14
  • $\begingroup$ 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. $\endgroup$ Sep 28, 2014 at 12:57
  • $\begingroup$ 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) ") $\endgroup$ Sep 28, 2014 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.