Technical Interview Question on Data Structures and Algorithms: Perfect Shuffle

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 CodeGround Online Testing PlatformCodeGround 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.

CodeGround supports Online Aptitude TestsSpoken English Communication Skills AssessmentsCoding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP.  CodeGround also supports Automated asynchronous interviews. CodeGround Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.

Please follow and like us:
0
Share this: