Tại sao thuật toán xáo trộn này sai?

Question

Trước khi tôi đọc về Fisher-Yates, đây là thuật toán tôi đã đưa ra:

def sort(arr): 
    for i in range(len(arr)): 
     swap(arr, i, rand.randint(0, len(arr) - 1)) 

Từ hiểu biết của tôi, sự khác biệt duy nhất giữa này và Fisher-Yates là thay vì:

swap(arr, i, rand.randint(0, len(arr) - 1)) 

Tôi nên viết:

swap(arr, i, rand.randint(i, len(arr) - 1)) 

Ai đó có thể giải thích cách thuật toán đầu tiên không chính xác? (ví dụ: không tạo ra ngẫu nhiên).

Answer 1

Từ Wikipedia:

Tương tự như vậy, luôn luôn chọn j từ toàn bộ phạm vi của chỉ số mảng hợp lệ trên mỗi iteration cũng tạo ra một kết quả đó là thiên vị, mặc dù ít rõ ràng như vậy. Điều này có thể được nhìn thấy từ thực tế là làm như vậy sản lượng n ⁿ trình tự khác biệt có thể có của các hoán đổi, trong khi chỉ có n! hoán vị có thể có của một mảng phần tử n. Vì n ⁿ không bao giờ có thể chia hết cho n! khi n> 2 (như sau chia hết cho n − 1, mà chia sẻ không có các thừa số nguyên tố với n), một số hoán vị phải được tạo ra bởi nhiều trình tự hoán đổi khác nhau. Như một ví dụ cụ thể về sự thiên vị này, hãy quan sát sự phân bố các kết quả có thể có của việc xáo trộn một mảng ba phần tử [1, 2, 3]. Có 6 hoán vị có thể có của mảng này (3! = 6), nhưng thuật toán tạo ra 27 khoảng trống có thể (33 = 27). Trong trường hợp này, [1, 2, 3], [3, 1, 2] và [3, 2, 1] mỗi kết quả từ 4 trong số 27 đợt xáo trộn, trong khi mỗi 3 hoán vị còn lại xảy ra ở 5 trong số 27 xáo trộn.

Về cơ bản, bạn đang đưa ra một xu hướng tinh tế vào trộn, điều này sẽ khiến một số hoán vị tăng lên thường xuyên hơn một chút. Nó thường không đáng chú ý, nhưng nó có thể làm cho một số ứng dụng nhạy cảm (ví dụ: mô phỏng Monte Carlo về hoán vị) không tạo ra câu trả lời chính xác.