## 簡介

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

## 實作

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]))

數字0分佈
99656,99624,100636,100081,99957,100149,100238,100287,99710,99662

100043,100292,99499,100262,100141,99847,100098,100164,99655,99999

100032,100412,99857,100035,100148,99738,100139,99765,99681,100193

100031,99868,100572,99418,99965,99918,99889,100107,100279,99953

100214,99716,100181,100315,99764,99667,100270,99829,99871,100173

99952,100282,99670,99642,99919,100401,99785,100627,100215,99507

100332,99879,99976,100143,99614,100319,99665,100169,100380,99523

99878,100407,99804,99669,100115,99760,100251,99602,100124,100390

100104,99888,99876,100575,100181,100229,100083,99398,99632,100034

99758,99632,99929,99860,100196,99972,99582,100052,100453,100566

## 不嚴謹的證明

Without loss of generality，令陣列為[0, 1, 2, …, n]

## 錯誤版本

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

數字0分佈
99993,100886,99773,100749,100077,99675,99556,99589,99798,99904

128185,93869,94816,95112,96020,96324,97355,98316,99545,100458

120180,124118,89932,91055,91953,92791,94813,96518,98183,100457

112478,115941,120497,86991,88766,90575,92353,94732,97465,100202

104476,109125,113448,119119,85554,88077,90897,92827,96727,99750

97764,101507,106920,112440,118047,85835,89281,92036,96476,99694

91910,96017,101046,105743,112624,119489,87594,91230,94797,99550

86177,90650,96260,101089,107061,113865,120411,90146,94617,99724

81888,86070,90840,96392,101840,109008,115726,124044,93945,100247

76949,81817,86468,91310,98058,104361,112014,120562,128447,100014

• 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