fisher-yates

Example:

例：

Say the input array is 
[1, 2 3, 4, 5 6, 7]
After reshuffling it can be anything like
[4, 3, 7, 2, 1, 5, 1]

Our goal is that the reshuffling should be as random as possible.

我們的目標是，改組應盡可能地隨機。

There is a standard algorithm named Fisher-Yates algorithm which shuffles the array in linear times.

有一個名為Fisher-Yates算法的標準算法，可以在線性時間內對數組進行隨機排序。

The idea is to start from an end

這個想法是從頭開始

Say we are string from the right end and the array size is n

假設我們是從右端開始的字符串，數組大小為n

Now, pick the end element which will be the nth element, and pick up another element randomly from the range [0, n-1]. Then swap the elements and shrink the right end. Thus after this step, a[n-1](the rightmost element) is fixed. Continue the same until we reach the left end.

現在，選擇將成為第n個元素的end元素，并從[0，n-1]范圍內隨機選擇另一個元素。 然后交換元素并縮小右端。 因此，在此步驟之后， a [n-1] (最右邊的元素)被固定。 繼續同樣操作，直到到達左端。

The detailed algorithm will be,

詳細的算法將是

For i=n-1 to 1
Pick and element in the range [0,i-1] randomly
Swap the randomly picked element with a[i]
Decrement i
End for loop

Since, it's random we can't do dry run

因為這是隨機的，所以我們不能空運行

But still to illustrate lets pick elements randomly as per thought

但仍需說明讓我們根據想法隨機選擇元素

So initially,
Array is
[1, 2 3, 4, 5 6, 7]
So i=6
Say, we picked up 4th (0-indexed) element randomly (in the range [0-5])
Swap them
So array is now
[1, 2, 3, 4, 7, 6, 5]
So 5 is now fixed and is guaranteed to stay 
there after the whole shuffling completes
On the next iteration
i will be 5 and we will continue similar way until I becomes 1

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
//reference to array is passed as we need 
//to update the array within the function
void reshuffle(vector<int>& arr, int n)
{
srand(time(0));
for (int i = n - 1; i >= 1; i--) {
//j will be a random no with in range 0 to i-1
int j = rand() % i;
//swap ith index with jth
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int main()
{
cout << "input array size\n";
int n;
cin >> n;
cout << "Input array elements \n";
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
reshuffle(arr, n);
cout << "After reshuffling, printing the array\n";
for (auto it : arr)
cout << it << " ";
cout << endl;
return 0;
}

Output:

輸出：

input array size
6
Input array elements
12 34 32 56 48 11
After reshuffling, printing the array
56 48 12 11 32 34

Real-life applications:

實際應用：

Creating an application which will suggest movie/songs from a list randomly. But each time it would suggest a unique movie only.

創建一個可以從列表中隨機建議電影/歌曲的應用程序。 但是每次都會只推薦一部獨特的電影。

In this case, what we will do is we will show the i^th indexed movie after each iteration. As the i^th indexed one is never going to come again in the reshuffling as that's being fixed every time. That means we will recommend ith song/movie after the swap is done at each stage.

在這種情況下，我們要做的是在每次迭代后顯示第i ^個索引的電影。 由于第i ^個被索引的索引永遠不會在改組中再次出現，因為每次都固定。 這意味著在每個階段完成交換后，我們將推薦第i首歌曲/電影。

Go through the below link to understand the detailed problem and solution.

瀏覽以下鏈接以了解詳細的問題和解決方案。

翻譯自: https://www.includehelp.com/data-structure-tutorial/shuffle-a-given-array-in-o-n-time-using-fisher-yates-shuffle-algorithm.aspx

fisher-yates