[Algo] 5.3 Randomized algorithms

對於 hiring problem，如果我們預先把 candidate 的 rank 作一次亂數排列，那麼我們就可以合理的假設我們每次都是得到一個 average case 的 input，而且在上一節我們已經證明出對於 average case 的 cost 是 $\ln n$，於是我們就可以不必擔心即使是 worst case 的 input。

@{
\proc{Randomized-Hire-Assistant}(n)
\li \textup{randomly permute the list of candidates}
\li best = 0\;\textup{// candidate 0 is a least-qualified dummy candidate}
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{interview candidate}\;i
\li \;\;\;\;\If \;\textup{candidate}\;i\;\textup{is better than candidate}\;best
\li \;\;\;\;\;\;\;\;best = i
\li \;\;\;\;\;\;\;\;\textup{hire candidate}\;i
}@




Randomly permuting arrays
我們接下來要看關於 RANDOMIZED-HIRE-ASSISTANT 裡面的隨機打亂 candidate 的順序的方法。課本裡提供了兩個方法，一個是 PERMUTE-BY-SORTING，另一個則是 RANDOMIZE-IN-PLACE。

(1) PERMUTE-BY-SORTING
假設 A 是一個包涵了從 1 到 n 的 array，這個方法是根據每個 A[i]都給予一個 priority P[i]，當然 P[i] 是由亂數決定的，接著我們根據 P 把 A 作排序的動作，即可達成我們的目的。

@{
\proc{Permute-By-Sorting}(A)
\li n = \textup{length}[A]
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;P[i] = \proc{Random}(1, n^3)
\li \textup{sort}\;A, \;\textup{using}\;P\;\textup{as sort keys}
\li \Return A
}@




在第3行的地方我們從 1 到$n^3$之間取出一個亂數，取這個範圍的目的是為了讓 P 裡面的亂數不會有重複的現象發生，課本更指出不會重複的機率大於等於 $1 - \frac{1}{n}$，我們給個小小的證明：
$\frac{P^{n^3}_n}{{(n^3)}^n} = \frac{n^3(n^3 - 1)\cdots(n^3-n+1)}{n^{3n}}$
$ = (1-\frac{0}{n^3})(1-\frac{1}{n^3})(1 - \frac{2}{n^3})\cdots(1-\frac{n-1}{n^3}) \geq (1-\frac{n}{n^3})^n$
$\geq 1 - \frac{1}{n}$        (if $a\mbox{,}b \geq 0 \Rightarrow (1 - a)(1 - b) \geq 1 - (a+b)$)

當然，最耗時間的步驟還是在第4行的地方，我們需要花費$\Theta(n \mbox{lg} n)$的時間來作排序。最後剩下要證明部份就是這個 procedure 是可以產生 uniform random permutation 的，在這裡證明的部份就暫時省略之。

(2) RANDOMIZE-IN-PLACE
這個方法比上一個方法好，他可以在$O(n)$的時間內就可以完成。

@{
\proc{Randomize-In-Place}(A)
\li n = \textup{length}[A]
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{swap}\;A[i]\;\textup{and}\;A[\proc{Random}(i,n)]
}@


要注意的是第3行，我們只從i到n的範圍裡去取出亂數，這樣子才會產生 uniform random permutation，如果我們取的是從1到n裡面的亂數，則不會是 uniform 的。