Home » Data Structure » Array Coding Problems

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 4^th (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 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.