CLRS Solutions | Exercise 5.3-6 | Probabilistic Analysis and Randomized Algorithms

Explain how to implement the algorithm $\textsc{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.

When two or more priorities are identical, we need a tie-breaking mechanism to ensure the relative order of tied elements is also randomized. Without this, elements with the same priority would maintain their original relative order, introducing bias.

The key insight is to create a composite key for sorting that combines the random priority with the original index. When priorities are equal, we break ties using a secondary randomized criterion.

Method 1: Two-Level Priority

Assign each element two values:

Primary priority: Random value from $[1, n^3]$
Secondary priority: Random value from $[1, n^3]$ (or even $[1, n^2]$)

Sort by the primary priority first, then by the secondary priority for ties.

$$\textsc{Permute-By-Sorting}'(A)$$$$\begin{aligned} 1& \quad n\,=\,A.length \\ 2& \quad \text{let}\,P[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 3& \quad \text{let}\,Q[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 4& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,n \\ 5& \quad \qquad P[i]\,=\,\textsc{Random}(1, \, n³) \\ 6& \quad \qquad Q[i]\,=\,\textsc{Random}(1, \, n³) \\ 7& \quad \\ 8& \quad \textbf{/\!/} \text{ Lexicographic}\,\text{ sort}\, \\ 9& \quad \text{sort}\,A\,\text{using}\,(P[i], \, Q[i])\,\text{as}\,\text{keys} \\ 10& \quad \textbf{return }\,A \\ \end{aligned}$$

In the sort, elements are compared first by $P$[$i$]. If $P$[$i$] = $P$[$j$], then we compare $Q$[$i$] and $Q$[$j$].

The probability of two elements having identical composite keys $(P[i], Q[i]) = (P[j], Q[j])$ is $1/n^6$, which is negligibly small. The probability that all $n$ composite keys are unique is at least $1 - n(n-1)/(2n^6) > 1 - 1/n^3$, which approaches 1 very quickly.

Method 2: Random Tiebreaker Values

A simpler approach assigns each element a unique tiebreaker that’s used only when priorities collide:

$$\textsc{Permute-By-Sorting-With-Ties}(A)$$$$\begin{aligned} 1& \quad n\,=\,A.length \\ 2& \quad \text{let}\,P[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 3& \quad \text{let}\,T[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 4& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,n \\ 5& \quad \qquad P[i]\,=\,\textsc{Random}(1, \, n³) \\ 6& \quad \qquad T[i]\,=\,\textsc{Random}(1, \, n³) \\ 7& \quad \\ 8& \quad \textbf{/\!/} \text{ Custom}\,\text{ comparison}\, \\ 9& \quad \textbf{if }\,P[i]\,\ne\,P[j] \\ 10& \quad \qquad \text{sort}\,A\,\text{using}\,P\,\text{as}\,\text{keys} \\ 11& \quad \textbf{else } \\ 12& \quad \qquad \text{sort}\,A\,\text{using}\,T\,\text{as}\,\text{keys} \\ 13& \quad \textbf{return }\,A \\ \end{aligned}$$

Method 3: Index-Based Tiebreaking with Randomization

We can use the original index as a tiebreaker, but randomize the comparison direction:

$$\textsc{Permute-By-Sorting-Index-Ties}(A)$$$$\begin{aligned} 1& \quad n\,=\,A.length \\ 2& \quad \text{let}\,P[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 3& \quad \textbf{/\!/} 0\text{ for}\,\text{ ascending,}\,1\text{ for}\,\text{ descending}\, \\ 4& \quad tiebreak\,=\,\textsc{Random}(0, \, 1) \\ 5& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,n \\ 6& \quad \qquad P[i]\,=\,\textsc{Random}(1, \, n³) \\ 7& \quad \\ 8& \quad \textbf{/\!/} \text{ Custom}\,\text{ comparison}\, \\ 9& \quad \textbf{if }\,P[i]\,\ne\,P[j] \\ 10& \quad \qquad \text{sort}\,A\,\text{using}\,P\,\text{as}\,\text{keys} \\ 11& \quad \textbf{else }\textbf{ if }\,tiebreak\,=\,0 \\ 12& \quad \qquad i\,<\,j \\ 13& \quad \textbf{else } \\ 14& \quad \qquad i\,>\,j \\ 15& \quad \\ 16& \quad \textbf{return }\,A \\ \end{aligned}$$

However, this method is less robust because it doesn’t fully randomize ties when there are more than two elements with the same priority (for example, if three elements all have the same priority, their relative order is still determined by their original indices).

Without proper tie-breaking, the algorithm would use the sorting algorithm’s default behavior for equal elements, which is typically stable sorting (maintaining original relative order). This would bias the output permutation.

For example, if $P = [5, 3, 3, 7]$ for array $A = [a, b, c, d]$, a stable sort would produce $[b, c, a, d]$, always keeping $b$ before $c$. With randomized tie-breaking, $[c, b, a, d]$ becomes equally likely, preserving uniformity.