Shuffle a given array in O(n) time using Fisher-Yates shuffle algorithm

In this article, we are going to see how to shuffle a given array in O(n) time using Fisher-Yates shuffling algorithm? This has very important applications in real-life products.
Submitted by Radib Kar, on July 13, 2020

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.

The idea is to start from an end

Say we are string from the right end and the array size is 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.

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:

#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 ith indexed movie after each iteration. As the ith 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.

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






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.