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

 
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 🙂
 

Get great deals at Amazon




Leave a Reply

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

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
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