隨機排序演算法實作

發表於 分類於 文章字數： 2.8k

簡介

說到隨機排序(shuffle)演算法，最著名的肯定是Fisher–Yates，它是一個$O(N)$時間的演算法，偽碼如下

1
2
3
4
5
6
Shuffle(Array a){
    N = a.length
    for (i = 0 ~ N-1){
        Swap(a[i], a[Random value between i and N])
    }
}

簡單來說就是每個元素都和之後(包含自身)的隨機一個元素交換

實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random

N = 10

def Shuffle(arr):
    for i in range(N-1):
        j = random.randint(i, N-1)
        arr[i], arr[j] = arr[j], arr[i]

total = [[0 for i in range(N)] for j in range(N)]
for t in range(1000000):
    arr = [i for i in range(N)]
    Shuffle(arr)
    for i, v in enumerate(arr):
        total[v][i] += 1

for i in range(N):
    print(f"數字{i}分佈")
    print(",".join(str(v) for v in total[i]))

執行1000000次Shuffle，各數字的分布

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
數字0分佈
99656,99624,100636,100081,99957,100149,100238,100287,99710,99662
數字1分佈
100043,100292,99499,100262,100141,99847,100098,100164,99655,99999
數字2分佈
100032,100412,99857,100035,100148,99738,100139,99765,99681,100193
數字3分佈
100031,99868,100572,99418,99965,99918,99889,100107,100279,99953
數字4分佈
100214,99716,100181,100315,99764,99667,100270,99829,99871,100173
數字5分佈
99952,100282,99670,99642,99919,100401,99785,100627,100215,99507
數字6分佈
100332,99879,99976,100143,99614,100319,99665,100169,100380,99523
數字7分佈
99878,100407,99804,99669,100115,99760,100251,99602,100124,100390
數字8分佈
100104,99888,99876,100575,100181,100229,100083,99398,99632,100034
數字9分佈
99758,99632,99929,99860,100196,99972,99582,100052,100453,100566

但為何只要這樣交換，就是隨機排序？ 🤔

不嚴謹的證明

已知N=1或2時，使用此法皆可使陣列為隨機排序。
若N=n時成立，考慮N=n+1時的情況：
Without loss of generality，令陣列為[0, 1, 2, ..., n]
第一個位置的數0會和後面的隨機一個元素交換，此時第一個位置是0到n的數的機率是平均的 $P_0(v)=\frac{1}{n+1}, v \in {0, 1, 2, .. n}$
此時子陣列([1:])即為N=n的情況，依照假設，使用此法後，其餘數字會是隨機排序，
所以N=n+1時也成立。
依數學歸納法，N=1,2時成立，且N=n成立時，N=n+1也成立；所以N為自然數時，使用此法皆可使陣列為隨機排序。$\blacksquare$

一個更直觀的解釋是，每一次交換都是在隨機選擇剩下還沒選的值。

錯誤版本

1
2
3
4
5
6
WrongShuffle(Array a){
    N = a.length
    for (i = 0 ~ N-1){
        Swap(a[i], a[Random value between 0 and N])
    }
}

此版本的所有元素對陣列中的一個元素交換
雖然接近，但不是隨機排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
數字0分佈
99993,100886,99773,100749,100077,99675,99556,99589,99798,99904
數字1分佈
128185,93869,94816,95112,96020,96324,97355,98316,99545,100458
數字2分佈
120180,124118,89932,91055,91953,92791,94813,96518,98183,100457
數字3分佈
112478,115941,120497,86991,88766,90575,92353,94732,97465,100202
數字4分佈
104476,109125,113448,119119,85554,88077,90897,92827,96727,99750
數字5分佈
97764,101507,106920,112440,118047,85835,89281,92036,96476,99694
數字6分佈
91910,96017,101046,105743,112624,119489,87594,91230,94797,99550
數字7分佈
86177,90650,96260,101089,107061,113865,120411,90146,94617,99724
數字8分佈
81888,86070,90840,96392,101840,109008,115726,124044,93945,100247
數字9分佈
76949,81817,86468,91310,98058,104361,112014,120562,128447,100014

為何不是隨機排序？ 🤔 目前想不到直觀解釋

參考維基的證明：
總共有$n^n$種選法，但可能的排列只有$n!$種，在$n>2$時並不能整除

更簡單的實作

對每個index設一隨機數，對隨機數排序
時間複雜度為$O(n\log n)$

各語言Shuffle實作

都是Fisher-Yates

  • Python
  • LLVM C++

Reference

  • Wiki
  • https://people.cs.umass.edu/~phaas/CS590M/handouts/Fisher-Yates-proof.pdf
  • https://cs.stackexchange.com/questions/2152/how-to-prove-correctness-of-a-shuffle-algorithm