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. At each iteration, the algorithm swaps the element with one chosen at random amongst all remaining unvisited elements, including the element itself. 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

 
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

 
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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Ricky Seltzer
Guest

The Fisher-Yates algorithm is not often practical, although it may do in a pinch.

Any method that depends on a rand() function or something similar (a PRNG) is not sufficient and cannot, with current hardware, meet the requirement that “Every permutation is equally likely”.

As an example take the task of shuffling a deck of cards for a computer game, possibly online, and possibly involving real money:

The number of permutations of a deck of cards is much greater than the number of permutations generated by a rand() function with a 64-bit seed.

Each 64-bit seed generates a unique permutation of the deck, so there are 2**64 permutations.

The number of permutations of a deck with 52 cards is 52!. This is almost 10**68.

52! is greater than 2**64 by a factor greater than 10**46. So the vast overwhelming number of permutations could never be generated.

If however, the machine had a word size of 226 bits, so that the rand() function would generate a number of distinct permutations greater than 52!, then the Fisher-Yates algorithm would work. In other words,
2**226 > 52!

Of course, a bignum package could also work around the difficulty at less cost.

John
Guest

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.

Nidhi Kesarwani
Guest

To swap, we don’t need to pass an array to the swap function. We can just pass the two elements by reference, is it useful? thanks.