Shuffle a given array of elements (Fisher–Yates shuffle)

Given an array of integers, in-place shuffle it. The algorithm should produce an unbiased permutation i.e. every permutation is equally likely.

 


 
Fisher–Yates shuffle is used to generate random permutations. It takes time proportional to the number of items being shuffled and shuffles them in place. Below is complete algorithm –


— To shuffle an array a of n elements :
for i from n-1 downto 1 do
    j = random integer such that 0 <= j <= i

    exchange a[j] and a[i]

C++

Download   Run Code

Java

Download   Run Code



Output: 4 6 1 2 5 3 (Random)
 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 


 
An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is:


— To shuffle an array a of n elements :
for i from 0 to n-2 do
    j = random integer such that i <= j < n

    exchange a[i] and a[j]

C++

Download   Run Code

Java

Download   Run Code



Output: 3 6 5 4 1 2 (Random)
 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Exercise:
Modify the code to generate random cyclic permutations of length n instead of random permutations (Sattolo’s algorithm).
 

Reference: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
John
Guest
John

Technically this can only satisfy the requirement of uniform selection from all possible permutations for arrays of size 21 or fewer, and probably much fewer. This is because the seed space has only 2^64 possible values, and 22! > 2^64.

wpDiscuz