Fisher-Yates算法会生成数组元素的随机排列,即它会随机随机排列数组的所有元素。由于Fisher-Yates算法是无偏的,因此数组的所有排列均具有相同的可能性。
给出了用于在C ++中实现Fisher-Yates算法以进行数组改组的程序-
#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; }
输出结果
上面程序的输出如下
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
在上面的程序中,数组的大小和数组是从用户请求的。这在下面给出-
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];
获得数组后,将index_arr []初始化为0。然后使用该rand()
函数将arr []的值随机存储到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]; }
最后,将显示改组后的数组。这在下面看到-
cout<<"The shuffled array is: "; for (int i = 0; i < n; i++) cout << arr1[i] << " ";