Thuật toán Fisher–Yates là cách chuẩn để máy tính xáo một bộ bài sao cho mọi thứ tự có xác suất bằng nhau. Ý tưởng chỉ một dòng: đi từ lá cuối về lá đầu, mỗi bước đổi lá hiện tại với một lá chọn ngẫu nhiên trong phần chưa xáo, kể cả chính nó. Viết sai một chi tiết nhỏ, chẳng hạn chọn lá trong toàn bộ bộ bài thay vì phần chưa xáo, là bộ bài bị lệch mà nhìn bằng mắt không hề thấy.
Nguồn gốc: từ bảng số trên giấy tới máy tính
Phương pháp mang tên hai nhà thống kê người Anh Ronald Fisher và Frank Yates, những người mô tả nó trong cuốn Statistical Tables for Biological, Agricultural and Medical Research năm 1938. Thời đó chưa có máy tính, nên cách làm là thủ công: viết dãy số từ 1 tới n, dùng bảng số ngẫu nhiên in sẵn để chọn một số trong những số còn lại, gạch nó đi và chép sang dãy mới, rồi lặp lại tới khi hết. Mục đích là xếp ngẫu nhiên các ô thí nghiệm đồng ruộng, không phải bài lá, nhưng bài toán là một.
Bản cho máy tính được Richard Durstenfeld công bố năm 1964 trên tạp chí Communications of the ACM, dưới tên "Algorithm 235: Random permutation". Điểm cải tiến là không cần gạch số rồi đếm lại: chỉ cần đổi chỗ lá được chọn với lá ở cuối phần chưa xáo. Cách làm này nhanh, gọn, không cần thêm bộ nhớ. Donald Knuth đưa nó vào tập 2 bộ sách The Art of Computer Programming, và từ đó nó thành bài học bắt buộc của dân lập trình. Nhiều tài liệu gọi nó là "thuật toán Knuth" vì vậy.
Thuật toán chạy thế nào
Đánh số các lá từ 0 tới n − 1. Phiên bản Durstenfeld:
- Cho i chạy từ n − 1 lùi về 1.
- Chọn ngẫu nhiên một số nguyên j trong khoảng từ 0 tới i, tính cả i, mỗi số có cơ hội như nhau.
- Đổi chỗ lá ở vị trí i với lá ở vị trí j.
Hết vòng lặp là xong. Với bộ bài 52 lá, máy chỉ làm 51 lần chọn số và 51 lần đổi chỗ. Thời gian chạy tỉ lệ thuận với số lá, cách xáo nhanh nhất có thể vì lá nào cũng phải được chạm tới ít nhất một lần.
Tự chạy tay với 5 lá
Bộ bài A B C D E ở các vị trí 0 tới 4. Giả sử các lần chọn ngẫu nhiên ra như sau:
| Bước | i | Khoảng chọn j | j rơi vào | Bộ bài sau bước |
|---|---|---|---|---|
| 1 | 4 | 0 – 4 | 2 | A B E D C |
| 2 | 3 | 0 – 3 | 3 | A B E D C (không đổi) |
| 3 | 2 | 0 – 2 | 0 | E B A D C |
| 4 | 1 | 0 – 1 | 1 | E B A D C (không đổi) |
Kết quả cuối cùng là E B A D C. Để ý: những bước "không đổi" là hoàn toàn bình thường, vì lá có quyền ở lại vị trí của mình.
Vì sao nó công bằng tuyệt đối
Lập luận đếm rất ngắn. Bước đầu có 5 lựa chọn cho j, bước hai có 4, bước ba có 3, bước bốn có 2. Tổng cộng 5 × 4 × 3 × 2 = 120 = 5! chuỗi lựa chọn, đúng bằng số thứ tự có thể có của 5 lá. Và mỗi chuỗi lựa chọn cho ra một thứ tự khác nhau, vì lá được đặt vào vị trí cuối ở mỗi bước là lá được chọn trong phần chưa động tới. Vậy 120 chuỗi ứng với đúng 120 thứ tự, mỗi thứ tự xuất hiện đúng một lần. Nếu mọi lựa chọn đều đều, mọi thứ tự có xác suất 1/120.
Một cách nói khác, gần với bộ bài thật: bước đầu chọn ngẫu nhiên lá nào nằm đáy bộ bài. Bước hai chọn ngẫu nhiên trong số còn lại lá nào nằm trên nó. Cứ thế. Đó chính xác là việc "rút ngẫu nhiên từng lá ra khỏi túi" mà ai cũng thấy là công bằng.
Lỗi kinh điển: chọn trong toàn bộ bộ bài
Phiên bản sai phổ biến nhất trông gần như giống hệt: với mỗi vị trí i, đổi lá ở đó với một lá ở vị trí ngẫu nhiên bất kỳ từ 0 tới n − 1. Nghe còn "ngẫu nhiên hơn". Nhưng hãy đếm: với n lá, có n × n × … × n = n^n chuỗi lựa chọn. Với 3 lá là 27 chuỗi, chia cho 6 thứ tự. 27 không chia hết cho 6, nên không thể nào mỗi thứ tự nhận số chuỗi bằng nhau.
Liệt kê đủ 27 chuỗi cho bộ 3 lá 1 2 3 ra kết quả:
| Thứ tự | Số chuỗi cho ra | Xác suất |
|---|---|---|
| 1 2 3 | 4 | 4/27 ≈ 14,8% |
| 1 3 2 | 5 | 5/27 ≈ 18,5% |
| 2 1 3 | 5 | 5/27 ≈ 18,5% |
| 2 3 1 | 5 | 5/27 ≈ 18,5% |
| 3 1 2 | 4 | 4/27 ≈ 14,8% |
| 3 2 1 | 4 | 4/27 ≈ 14,8% |
Mức đúng phải là 1/6 ≈ 16,7% cho mỗi dòng. Với 4 lá, cách sai có 256 chuỗi chia cho 24 thứ tự, thứ tự được ưu ái nhất nhận 15 chuỗi còn thứ tự bị thiệt nhất chỉ 8, chênh gần gấp đôi. Bộ bài càng lớn thì độ lệch càng khó thấy bằng mắt nhưng vẫn luôn tồn tại, vì n^n không bao giờ chia hết cho n! khi n từ 3 trở lên.
Lỗi thứ hai: lấy phần dư làm lệch số
Thuật toán đúng đòi hỏi bước chọn j phải thật sự đều. Nhiều chương trình lấy một số ngẫu nhiên lớn rồi chia lấy dư cho số lựa chọn. Nếu khoảng số ban đầu không chia hết cho số lựa chọn, sẽ có lệch.
Ví dụ tính tay: một byte ngẫu nhiên cho các số 0 tới 255, tức 256 giá trị. Lấy dư khi chia cho 52 để chọn một lá. Vì 256 = 4 × 52 + 48, các phần dư từ 0 tới 47 xuất hiện 5 lần, còn 48 tới 51 chỉ 4 lần. Bốn lá cuối bị chọn ít hơn các lá khác 20%. Cách sửa là loại bỏ: nếu số rơi vào đoạn thừa từ 208 tới 255 thì bỏ, rút số khác. Các thư viện lập trình hiện đại đều làm sẵn bước này, nên tốt nhất là dùng hàm xáo của thư viện thay vì tự viết.
Các biến thể đáng biết
- Bản Fisher–Yates gốc: gạch số trên giấy, đúng nhưng chậm nếu làm bằng máy, vì mỗi bước phải đếm lại các số chưa gạch.
- Bản "từ trong ra ngoài": dựng bộ bài đã xáo ngay trong lúc đọc từng lá vào, hợp khi chưa biết trước tổng số lá.
- Thuật toán Sattolo (1986): chỉ đổi khoảng chọn j thành 0 tới i − 1, bỏ chính i. Kết quả không còn là mọi thứ tự nữa mà chỉ là các hoán vị tạo thành một vòng duy nhất. Hữu ích khi cần, chẳng hạn, xếp lịch rút thăm tặng quà để không ai tự rút trúng mình và mọi người nối thành một vòng.
- Xáo một phần: nếu chỉ cần 7 lá đầu ngẫu nhiên, chạy 7 bước là đủ, không cần xáo cả bộ.
Góc nhìn hôm nay: kiểm một bộ xáo bài
Muốn biết một chương trình xáo bài có công bằng không, cách đơn giản nhất là thử với bộ bài nhỏ. Xáo bộ 3 lá khoảng sáu trăm nghìn lần, đếm số lần mỗi thứ tự xuất hiện. Bộ xáo đúng sẽ cho sáu con số quanh 100 000, lệch nhau cỡ vài trăm. Bộ xáo sai kiểu "chọn trong toàn bộ" sẽ cho ba con số quanh 89 000 và ba con số quanh 111 000: không thể nhầm.
Một điều cần nhớ nữa: Fisher–Yates chỉ công bằng khi nguồn số ngẫu nhiên đủ tốt. Một bộ sinh số chỉ có vài tỷ trạng thái thì dù thuật toán đúng, nó cũng chỉ có thể sinh ra vài tỷ thứ tự trong số 52! ≈ 8 × 10^67. Phần đó là chuyện của số ngẫu nhiên giả và "hạt giống", có bài riêng trong danh mục này.
Đọc thêm: tập 2 của The Art of Computer Programming (Knuth), chương về số ngẫu nhiên, trình bày thuật toán cùng chứng minh, và là tài liệu gốc mà gần như mọi giáo trình về sau đều dẫn lại.
Câu hỏi thường gặp
Thuật toán Fisher–Yates là gì?
Là thuật toán xáo ngẫu nhiên một dãy sao cho mọi thứ tự có xác suất bằng nhau. Đi từ phần tử cuối về đầu, mỗi bước đổi phần tử hiện tại với một phần tử chọn đều trong phần chưa xáo, kể cả chính nó.
Ai nghĩ ra thuật toán Fisher–Yates?
Ronald Fisher và Frank Yates mô tả bản làm bằng giấy bút năm 1938. Richard Durstenfeld đưa ra bản cho máy tính năm 1964, và Donald Knuth phổ biến nó trong bộ sách The Art of Computer Programming, nên còn gọi là thuật toán Knuth.
Vì sao đổi chỗ với một vị trí bất kỳ lại sai?
Vì cách đó có n mũ n chuỗi lựa chọn, mà con số này không chia hết cho n! khi n từ 3 trở lên, nên các thứ tự không thể có xác suất bằng nhau. Với 3 lá, ba thứ tự có xác suất 5/27, ba thứ tự còn lại chỉ 4/27.
Xáo 52 lá bằng Fisher–Yates mất bao nhiêu bước?
Đúng 51 lần chọn số ngẫu nhiên và tối đa 51 lần đổi chỗ. Số bước tăng tỉ lệ thuận với số lá, nhanh nhất có thể cho bài toán xáo.
Thuật toán Sattolo khác Fisher–Yates thế nào?
Sattolo chỉ khác ở chỗ không cho phần tử được chọn chính nó. Kết quả luôn là một hoán vị một vòng duy nhất, không phải mọi thứ tự, rất hợp cho việc rút thăm tặng quà vòng tròn.
