Trình Xáo Trộn Danh Sách Ngẫu Nhiên - Công Cụ Trộn Danh Sách Trực Tuyến Miễn Phí

Trình xáo trộn danh sách ngẫu nhiên là gì?

Trình xáo trộn danh sách ngẫu nhiên là công cụ nhận một danh sách các mục và sắp xếp chúng lại theo một thứ tự mới, ngẫu nhiên. Nhập tên, nhiệm vụ hoặc bất kỳ nội dung nào khác, mỗi mục trên một dòng, rồi công cụ sẽ sắp xếp lại để mọi thứ tự có thể xảy ra đều có cơ hội xuất hiện như nhau. Công cụ này sử dụng thuật toán xáo trộn Fisher–Yates, một thuật toán nổi tiếng để tạo ra các thứ tự ngẫu nhiên không thiên lệch.

Cách sử dụng trình xáo trộn danh sách ngẫu nhiên

1. Nhập hoặc dán danh sách vào ô, mỗi mục trên một dòng.
2. Nhấp vào "Ngẫu nhiên hóa danh sách". Các mục sẽ được sắp xếp lại ngay lập tức.
3. Đọc danh sách đã xáo trộn bên dưới nút, được đánh số theo thứ tự mới.
4. Nhấp lại vào "Ngẫu nhiên hóa danh sách" để thực hiện một lần xáo trộn mới, độc lập.
5. Nhấp vào "Sao chép kết quả" để sao chép thứ tự mới, hoặc "Xóa" để bắt đầu lại.

Các dòng trống trong dữ liệu nhập sẽ tự động bị loại bỏ, vì vậy các ngắt dòng thừa sẽ không tạo ra mục trống trong kết quả.

Thuật toán xáo trộn Fisher-Yates hoạt động như thế nào?

Phép xáo trộn Fisher–Yates duyệt qua danh sách một lần, bắt đầu từ mục cuối cùng và tiến dần về đầu danh sách. Ở mỗi bước, nó chọn ngẫu nhiên một mục trong phần danh sách chưa được đặt, rồi đổi mục đó vào vị trí hiện tại.

Công thức xáo trộn Fisher-Yates

Với danh sách gồm n mục, được đánh số từ vị trí 0 đến vị trí n − 1:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

Vòng lặp chạy n − 1 lần, nên toàn bộ phép xáo trộn mất khoảng n bước. Đây được gọi là thời gian tuyến tính, viết là O(n). Vì thuật toán xét mỗi vị trí đúng một lần và chọn từ một tập mục được xác định rõ, thu hẹp dần, nên mỗi thứ tự trong số n! (giai thừa của n: n × (n − 1) × ... × 1) đều có cùng xác suất trở thành kết quả.

Ví dụ: xáo trộn danh sách gồm bốn mục

Bắt đầu với bốn mục ở các vị trí từ 0 đến 3: Apple, Banana, Cherry, Date.

• i = 3: mục được chọn ngẫu nhiên là j = 0. Đổi vị trí 3 và 0 → Date, Banana, Cherry, Apple
• i = 2: mục được chọn ngẫu nhiên là j = 2. Đổi một vị trí với chính nó không làm thay đổi gì → Date, Banana, Cherry, Apple
• i = 1: mục được chọn ngẫu nhiên là j = 0. Đổi vị trí 1 và 0 → Banana, Date, Cherry, Apple

Thứ tự cuối cùng: Banana, Date, Cherry, Apple.

Với bốn mục, có 4! = 24 thứ tự có thể xảy ra. Mỗi thứ tự, bao gồm cả thứ tự này, có cơ hội 1 trên 24 xuất hiện trong bất kỳ lần xáo trộn nào.

Tại sao không chỉ đổi các cặp ngẫu nhiên?

Một phương pháp có vẻ đơn giản hơn — chọn hai vị trí ngẫu nhiên và đổi chúng, lặp lại vài lần — trông có vẻ ngẫu nhiên nhưng thực ra không phải vậy. Một số chương trình xáo trộn đầu tiên từ những năm 1950 hoạt động theo cách này và âm thầm ưu tiên một số thứ tự hơn các thứ tự khác, dù không có lần chạy riêng lẻ nào trông đáng ngờ. Phép xáo trộn Fisher–Yates tránh được điều này vì mỗi mục được di chuyển đúng một lần, vào một vị trí được chọn từ một tập lựa chọn thu hẹp chính xác, nhờ đó mọi thứ tự cuối cùng đều có khả năng xảy ra như nhau.

Phép xáo trộn Fisher-Yates bắt nguồn từ đâu?

Các nhà thống kê Ronald Fisher và Frank Yates mô tả phương pháp này vào năm 1938 trong một cuốn sách về các bảng thống kê, nhằm xáo trộn thủ công khi thiết kế thí nghiệm. Vào năm 1964, Richard Durstenfeld điều chỉnh phương pháp này cho máy tính để có thể sắp xếp lại danh sách ngay tại chỗ mà không cần một danh sách thứ hai để theo dõi các mục còn lại. Donald Knuth đưa phiên bản máy tính này vào cuốn sách Nghệ thuật lập trình máy tính xuất bản năm 1969, vì vậy đôi khi nó còn được gọi là phép xáo trộn Knuth. Các trình duyệt web ngày nay cũng sử dụng cùng thuật toán này.

Những cách sử dụng phổ biến của trình xáo trộn danh sách

• Thiết lập thứ tự học sinh thuyết trình hoặc trả lời câu hỏi trong lớp
• Chọn hạt giống cho nhánh đấu của giải đấu hoặc thiết lập thứ tự lượt chơi
• Chia một nhóm thành các đội ngẫu nhiên
• Chọn nhà hàng, bộ phim hoặc nhiệm vụ từ một danh sách rút gọn mà không thiên vị lựa chọn nào

Xáo trộn thông thường không phải lúc nào cũng phù hợp. Nếu một số mục cần xuất hiện thường xuyên hơn các mục khác, chọn mẫu có trọng số sẽ phù hợp hơn. Nếu cần bảo đảm mọi nhóm đều được đại diện, lấy mẫu phân tầng sẽ hiệu quả hơn một lần xáo trộn ngẫu nhiên duy nhất.

Các câu hỏi thường gặp

Phép xáo trộn có thực sự ngẫu nhiên không?

Công cụ dựa vào bộ sinh số giả ngẫu nhiên (PRNG) của trình duyệt web, một công thức tạo ra các chuỗi số có tính chất giống ngẫu nhiên cho các mục đích thực tế. Cách này đủ tốt để sắp xếp trong lớp học, chọn hạt giống cho giải đấu hoặc chọn phim. Nó không được thiết kế cho mật mã, hệ thống cờ bạc hoặc bất kỳ trường hợp nào mà tiền bạc hay an ninh phụ thuộc vào tính khó đoán; những trường hợp đó cần các bộ sinh số ngẫu nhiên được chứng nhận.

Công cụ có gửi danh sách của tôi đến máy chủ không?

Bản thân phép xáo trộn chạy hoàn toàn trong trình duyệt bằng JavaScript, nên không cần yêu cầu mạng để sắp xếp lại danh sách. Danh sách hiện tại cũng được ghi vào địa chỉ web của trang, vì vậy việc tải lại trang hoặc lưu dấu trang sẽ không làm mất danh sách. Nếu địa chỉ đó được sao chép, chia sẻ hoặc mở lại, danh sách sẽ đi kèm với địa chỉ, kể cả đến bất kỳ máy chủ nào sau đó tải trang. Nếu điều này đáng lo ngại, không nên đưa thông tin nhạy cảm vào danh sách.

Điều gì xảy ra với các mục trùng lặp?

Các mục trùng lặp được giữ nguyên. Nếu "Sam" xuất hiện hai lần trong dữ liệu nhập, nó vẫn sẽ xuất hiện hai lần trong kết quả đã xáo trộn, có thể ở các vị trí khác nhau.

Có giới hạn về số lượng mục có thể xáo trộn không?

Công cụ không đặt ra giới hạn nào. Vì phép xáo trộn chạy trong thời gian tuyến tính, ngay cả các danh sách dài cũng được sắp xếp lại trong một phần nhỏ của giây trên mọi thiết bị hiện đại.

Xáo trộn khác với sắp xếp như thế nào?

Sắp xếp bố trí các mục theo một quy tắc cố định, chẳng hạn như thứ tự bảng chữ cái, và luôn cho cùng một kết quả với cùng dữ liệu đầu vào. Xáo trộn sắp xếp các mục một cách ngẫu nhiên và tạo ra một thứ tự khác gần như mỗi lần, ngay cả khi dữ liệu đầu vào giống hệt nhau.

Có thể xáo trộn cùng một danh sách nhiều lần không?

Có. Mỗi lần nhấp vào "Ngẫu nhiên hóa danh sách", thuật toán lại chạy độc lập với mọi lần xáo trộn trước đó. Với danh sách nhỏ, việc lặp lại một thứ tự là điều có thể xảy ra do ngẫu nhiên; với danh sách lớn hơn, khả năng này cực kỳ thấp.