演算法›Ch1 Introduction第 2 題/共 4 題
2. 隨機演算法、Fisher-Yates
#AL-01-002中隨機演算法Fisher-Yates
Which of the following generates a uniformly random permutation of an array of size in place, assuming that RANDOM() returns an integer chosen uniformly at random from ?
RANDOM-PERMUTE(A) 1 for i = 1 to n 2 □ 3 if a <= b 4 swap A[i] with A[RANDOM(a,b)]
參考答案與解析
答案 (C):即 CLRS 的 RANDOMIZE-IN-PLACE,正確作法是 a=i, b=n,每輪把 A[i] 與 A[i..n] 中隨機一個位置互換。可用歸納法證明:第 i 輪執行後,A[1..i] 是原陣列任 i 個元素的均勻隨機排列。若像(B)那樣改成跟前面 i-1 個交換,則之後被選中的元素無法再被换到後面的位置,會破壞均勻性。
📄 台大115
▤完整推導請見《WH 資工筆記 · 演算法》Ch1 Introduction