Chương trình C++ triển khai thuật toán Fisher-Yates xáo trộn mảng

Thuật toán Fisher-Yates tạo ra một hoán vị ngẫu nhiên của các phần tử mảng, đảm bảo mọi hoán vị đều có xác suất như nhau (unbiased).

Ví dụ

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
    int n;
    cout << "Enter the array size: " << endl;
    cin >> n;
    int arr[n], arr1[n], index_arr[n];
    int index;
    cout << "Enter the array elements: " << endl;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++)
        index_arr[i] = 0;
    for (int i = 0; i < n; i++) {
        do {
            index = rand() % n;
        } while (index_arr[index] != 0);
        index_arr[index] = 1;
        arr1[i] = arr[index];
    }
    cout << "The shuffled array is: ";
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";
    return 0;
}

Kết quả

Enter the array size: 10
Enter the array elements: 1 2 3 4 5 6 7 8 9 10
The shuffled array is: 4 7 8 6 3 10 2 1 9 5

Chương trình yêu cầu kích thước và các phần tử mảng từ người dùng:

cout << "Enter the array size: " << endl;
cin >> n;
int arr[n], arr1[n], index_arr[n];
int index;
cout << "Enter the array elements: " << endl;
for (int i = 0; i < n; i++)
    cin >> arr[i];

Sau đó khởi tạo index_arr[] bằng 0. Sử dụng rand() để chọn ngẫu nhiên vị trí chưa dùng, lưu vào mảng mới arr1[]:

for (int i = 0; i < n; i++) {
    do {
        index = rand() % n;
    } while (index_arr[index] != 0);
    index_arr[index] = 1;
    arr1[i] = arr[index];
}

Cuối cùng in mảng đã xáo trộn:

cout << "The shuffled array is: ";
for (int i = 0; i < n; i++)
    cout << arr1[i] << " ";