+1-315-215-3377
+91-9980992834

Technical Interview Question on Data Structures and Algorithms: Perfect Shuffle

Recruitment Made Easy

perfect-shuffle

What is an unbiased Shuffle algorithm?

Consider an array with distinct elements A[1 … n] A perfectly unbiased shuffle algorithm would randomly shuffle all elements in the array such that after shuffling:
1.The probability that the shuffling operation would produce any particular permutation of the original array is the same for all permutations (i.e.) since there are n! permutations, the probability that the shuffle operation would produce any particular permutation is 1/n!
2.For any element e in the array and for any position j (1<= j <= n), the probability that the element would end up in position A[j] is 1/n

Consider two shuffling algorithms

SHUFFLE 1

shuffle(A[1 … n])   {
    for i = 1 to n   {
        // Find a random integer between 1 and n inclusive
        int rand= RANDOM(1,n);
        swap A[i] with A[rand];
    }
}

SHUFFLE 2

shuffle(A[1 … n])   {
    for i = 1 to n   {
        // Find a random integer between i and n inclusive
        int rand= RANDOM(i,n);
        swap A[i] with A[rand];
    }
}

How do these two shuffling algorithms compare against each other? Let’s simulate and find out.

Simulation of Shuffle 1

A simulation of Shuffle 2 with an array of is given below.
simulation-of-shuffle-1
Count of permutations:
{1,2,3} – count 4
{1,3,2} – count 5
{2,1,3} – count 5
{2,3,1} – count 5
{3,1,2} – count 4
{3,2,1} – count 4
Conclusion: Shuffle 1 is biased

Simulation of Shuffle 2

A simulation of Shuffle 2 with an array {1,2,3} is given below.
simulation-of-shuffle-2
Count of permutations:
{1,2,3} – count 1
{1,3,2} – count 1
{2,1,3} – count 1
{2,3,1} – count 1
{3,1,2} – count 1
{3,2,1} – count 1
Conclusion: Shuffle 2 is an unbiased perfect shuffling algorithm

Can we prove that Shuffle 2 will produce an unbiased shuffle in all cases?

For any element e, the probability that it will be shuffled into the first position
= probability that it is selected for swapping when i = 1
= 1/n
For any element e, the probability that it will be shuffled into the second position
= probability that it is NOT selected for the first position x probability that it is selected for swapping when i = 2
= (n-1)/n   x   1/(n-1)
= 1/n

For any element e, the probability that it will be shuffled into any particular position = 1/n

This content was brought to you by Evalground Online Testing PlatformEvalground is an online assessment and test evaluation system focused on helping Recruiters in initial screening of potential candidates from an ocean of job seekers in an automated way.
Evalground supports Online Aptitude Tests, Spoken English Communication Skills AssessmentsCoding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP.  Evalground also supports Automated asynchronous interviews. Evalground Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.

Sharing is caring!