Chương trình C ++ để triển khai thuật toán Fisher-Yates để 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, tức là nó xáo trộn ngẫu nhiên tất cả các phần tử của một mảng. Tất cả các hoán vị cho mảng đều có khả năng như nhau vì thuật toán Fisher-Yates là không thiên vị.

Một chương trình triển khai Thuật toán Fisher-Yates để xáo trộn mảng trong C ++ được đưa ra như sau -

Ví dụ

#include <iostream>
#include <t;stdlib.h>
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;
}

Đầu ra

Kết quả của chương trình trên như sau

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

Trong chương trình trên, kích thước của mảng và mảng được yêu cầu từ người dùng. Điều này được đưa ra dưới đây -

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 khi mảng được lấy, index_arr [] được khởi tạo bằng 0. Sau đó, hàm rand () được sử dụng để lưu trữ ngẫu nhiên các giá trị của arr [] vào arr1 []. Điều này được chứng minh bằng đoạn mã sau -

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 mảng xáo trộn được hiển thị. Điều này được nhìn thấy bên dưới -

cout<<"The shuffled array is: ";

for (int i = 0; i < n; i++)
cout << arr1[i] << " ";