4
$\begingroup$

I'm studying Algorithms by Jeff Erickson. Consider this exercise from that textbook:

Prove that the following algorithm, modeled after quicksort, uniformly permutes its input array, meaning each of the $n!$ possible output permutations is equally likely. [Hint: $ \binom{n}{k} =\frac{n!}{k!(n-k)!} $]

$\quad\text{QuickShuffle}(A[1\cdot\cdot n])$:
$\quad\quad$if $n ≤ 1$
$\quad\quad\quad$return
$\quad\quad j \leftarrow 1; k \leftarrow n$
$\quad\quad$while $j \le k$
$\quad\quad\quad$with probability $1/2$
$\quad\quad\quad\quad$swap $A[j] \leftrightarrow A[k]$
$\quad\quad\quad\quad k \leftarrow k − 1$
$\quad\quad\quad$else
$\quad\quad\quad\quad j \leftarrow j + 1$
$\quad\quad\text{QuickShuffle}(A[1..k])$
$\quad\quad\text{QuickShuffle}(A[j..n])$

My attempt: To solving above problem, I think we should achieve below
$$\frac{1}{\binom{n}{k}}\frac{1}{k!}\frac{1}{(n-k)!}=\frac{1}{n!}$$ but how we can achieve above to solve the problem?

$\endgroup$
1
  • $\begingroup$ It turns out that hint is not necessary for a proof. $\endgroup$
    – John L.
    Apr 1, 2022 at 3:54

2 Answers 2

1
$\begingroup$

This exercise is interesting. One key idea is to understand the effect of the while loop. It may help if you try exercise 2 below first, since exercise 2 is a generalization.


Let us fix the input $A$. WLOG, assume all $n$ elements in $A$ are distinct.

Since the only kind of change made to $A$ is a swap, $A[j]\leftrightarrow A[k]$, $A$ at the end of the algorithm is a permutation of the original $A$ given as the input.

Characterization of $A[1..k]$ right after the while loop

Consider a subset $B\subseteq A$.

Claim. There is a unique series of choices made by the while loop such that right after the while loop, $k=|B|$ and $\text{set}(A[1..k])=B$.

Proof. The while loop rearranges input $A$ into two parts, the front part $A[1..k]$ and the back part $A[k+1..n]$. Note that $k$, which is $n$ initially, can be decreased only and $j$, which is $1$ initially, can be increased only. Right after the while loop, $j=k+1$.

How can we let the while loop can end up with $k=|B|$ and $\text{set}(A[1..k])=B$?

Viewing $A$ as a double-ended queue, each iteration of the while loop polls one number from either end of the queue and then puts it into one of the two parts.

For each iteration of the while loop, if $A[j]\not\in B$, do the swap and decrease $k$, which includes $A[j]$ in the back part. Otherwise, increase $j$, which includes $A[j]$ in the front part.

It is easy to check this series of choices will ensure $k=|B|$ and $\text{set}(A[1..k])=B$ right after the while loop and it is the only possible series of choices to achieve that effect. $\quad\checkmark$

Since that series of choices is unique, right after the while loop, $A$ is completely determined by $\text{set}(A[1..k])$.

The algorithm uniformly permutes the input

Proof. Do induction on $n$.

For the base case, $n=1$, it is true trivially.

Let $n\ge2$. Suppose it is true for smaller $n$. Suppose $P=(P[1], P[2], \cdots, P[n])$ is a permutation of $A$.

How can we compute the probability of the algorithm to produce $P$?

For the algorithm to produce $P$, it is necessary and sufficient that at the end of the while loop,

  1. $\text{set}(A[1..k])=\text{set}(P[1..k])$, and
  2. after $\text{QuickShuffle}(A[1..k])$, $A[1..k]=P[1..k]$ and
  3. after $\text{QuickShuffle}(A[k+1..n])$, $A[k+1..n]=P[k+1..n]$

All possible values of $k$ right after the while loop are $0, 1, 2, \cdots, n$. Thanks to the claim above, for each possible value, there is a unique series of $n$ choices made in the while loop such that right after the while loop $k$ is that number and $\text{set}(A[1..k])=\text{set}(P[1..k])$, i.e., condition 1 happens on $n$ disjoint situations, each with probability $2^{-n}$.

Once condition 1 is satisfied for a particular $k$, $A[1..k]$ and $A[k+1..n]$ are determined. Thanks to the induction hypothesis, if $k\neq0$,

  • condition 2 is satisfied with probability $1/k!$ and
  • condition 3 is satisfied with probability $1/(n-k)!$ independently.

If condition 1 is satisfied with $k=0$, which happens with probability $2^{-n}$, condition 2 will always be satisfied and the algorithm will be calling itself exactly the same in its last step, "$\text{QuickShuffle}(A[1..n])$".

If condition 1 is satisfied with $k=n$, which happens with probability $2^{-n}$, condition 3 will always be satisfied and the algorithm will be calling itself exactly the same in its second to last step, "$\text{QuickShuffle}(A[1..n])$".

We see that the computation above of the probability of the algorithm producing $P$ does not dependent on the particular choice of $P$. The induction step is complete. $\quad\checkmark$

Two exercises

Exercise 1. Although complete, the proof above does not compute the probability of the algorithm producing $P$. Compute it explicitly. You should obtain $\displaystyle\frac1{n!}$.

Exercise 2. Prove the following algorithm permutes its input array uniformly.

$\quad\text{QuickShuffleGeneral}(A[1\cdot\cdot n])$:
$\quad\quad$if $n ≤ 1$
$\quad\quad\quad$return
$\quad\quad$Let $B$ be chosen from all subsets of $\text{set}(A)$ uniformly. Let $C=\text{set}(A)\setminus B$.
$\quad\quad$Put $B$ in $A[1..|B|]$. Call $\text{QuickShuffleGeneral}(A[1..|B|])$
$\quad\quad$Put $C$ in $A[|B|+1..n]$. Call $\text{QuickShuffleGeneral}(A[|B|+1..n])$

$\endgroup$
0
$\begingroup$

Here is a (in my opinion) simpler argument than John L.'s and the one the book suggests with its hint.

Note that (if the array has more than 1 element) the main loop of QuickShuffle partitions the array in two, $A[1..k]$ and $A[k+1..n]$, and each element in $A$ has a 50% chance of ending up in either partition. Then we recurse on both partitions. We can phrase the algorithm thusly:

  1. Flip a coin for each element of $A$, and assign 0 for tails and 1 for heads.
  2. Partition the array so that all elements with a 0 come first, and 1 come after.
  3. Recurse on each partition.

Now for each element we can look at the series of coinflips that determined its final location in the array. But before doing so we add a 0. in front of the sequence, and ... after. For example for shuffling [a, b, c, d, e, f]:

a 0.000...
c 0.001...
f 0.10...
d 0.1100...
b 0.1101...
e 0.111...

What we have implicitly done is associated a uniformly random real number in $[0, 1)$ (with an infinite amount of digits!) with each element, written fractional binary, only expanding out those digits necessary to distinguish the order between the real numbers. Note that ties are impossible, the algorithm would keep recursing until the prefix of the infinite stream of digits is distinct from all others as a tie would imply both numbers ended up in the same partition.

In other words, our algorithm is equivalent to associating a distinct random real number to each element and sorting based on that number, which is a classic algorithm for getting a uniformly random permutation.

$\endgroup$

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.