Thuật toán xáo trộn Fisher-Yates
Thuật toán này là xáo trộn các phần tử trong một mảng. Để xáo trộn các phần tử trong một mảng, chúng ta có thể viết logic của riêng mình, nhưng nhiều nhà phát triển nghĩ rằng F isher-Yates thuật toán xáo trộn hiện đại là cách tốt nhất để xáo trộn các phần tử trong một mảng. Thuật toán này có các bước sau.
Các bước cần làm theo
- Theo thuật toán này, chúng ta nên lặp mảng từ sau ra trước. Ví dụ, trong ví dụ sau, chúng ta có một mảng bao gồm 8 phần tử (A, B, C, D, E, F, G, H) từ chỉ số 0 đến chỉ số 7. Vì vậy, vòng lặp đầu tiên sẽ ảnh hưởng đến phần tử tại chỉ số 7 cuối cùng là H.
- Bước tiếp theo là tạo một số ngẫu nhiên (chỉ số ngẫu nhiên) giữa chỉ số đã chọn 7 và chỉ số 0. Ví dụ, giả sử chỉ số ngẫu nhiên là 3.
- Sau khi nhận được chỉ mục ngẫu nhiên, hãy hoán đổi các phần tử có trong chỉ mục đã chọn và ở chỉ mục ngẫu nhiên. Phần tử ở chỉ mục ngẫu nhiên trong mảng được cung cấp là D. Vì vậy, sau khi hoán đổi, mảng sẽ được thay đổi thành A, B, C , H, E, G, F, D.
- Trong vòng lặp thứ hai, chỉ cần bỏ qua chỉ mục cuối cùng (vì nó đã được lặp lại) và cố gắng tìm chỉ số ngẫu nhiên giữa chỉ số 0 và chỉ số 6 nằm giữa các phần tử A và F. Hãy để chỉ số ngẫu nhiên được tạo là 2.
- Sau khi nhận được chỉ mục ngẫu nhiên, hãy hoán đổi các phần tử tại các chỉ mục ở 6 và 2. Bây giờ mảng sẽ có dạng A, B, F, H, E, G, C, D.
- Thuật toán này tuân theo cùng một mẫu đó là nó bỏ qua chỉ mục 6 và bắt đầu tìm chỉ mục ngẫu nhiên giữa chỉ mục 5 và chỉ mục 0, v.v. cho đến khi đạt đến chỉ mục 1. Không thể lặp chỉ mục 0 vì không có chỉ mục nào nhỏ hơn 0 cho mục đích hoán đổi.
- Lưu ý rằng có khả năng chỉ mục ngẫu nhiên được tạo là chỉ mục vòng lặp được chọn. Ví dụ:hãy để vòng lặp đang chạy giữa chỉ số 4 đã chọn và chỉ số 0. hãy để chỉ mục ngẫu nhiên được tạo là 4. Khi đó giá trị ở chỉ số 4 sẽ vẫn ở vị trí cũ.
Ví dụ sau minh họa Fisher-Yates thuật toán xáo trộn hiện đại
Ví dụ
<html>
<body>
<script>
var arr = ['A','B','C','D','E','F','G','H']
var i = arr.length, k , temp; // k is to generate random index and temp is to swap the values
while(--i > 0){
k = Math.floor(Math.random() * (i+1));
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
document.write(arr);
</script>
</body>
</html> Đầu ra
C,F,H,D,A,G,E,B // note that output will change for every iteration.