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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <stdio.h> // Utility function to swap two elements A[i] and A[j] in the array void swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Function to shuffle an array A[] of n elements void shuffle(int A[], int n) { // read array from highest index to lowest for (int i = n - 1; i >= 1; i--) { // generate a random number j such that 0 <= j <= i int j = rand() % (i + 1); // swap current element with randomly generated index swap(A, i, j); } } // main function int main(void) { int A[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(A) / sizeof(A[0]); // seed for random input srand(time(NULL)); shuffle(A, n); // print the shuffled array for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.util.Arrays; import java.util.Random; class Shuffle { // Utility function to swap two elements A[i] and A[j] in the array private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Function to shuffle an array A[] public static void shuffle(int A[]) { // read array from highest index to lowest for (int i = A.length - 1; i >= 1; i--) { Random rand = new Random(); // generate a random number j such that 0 <= j <= i int j = rand.nextInt(i + 1); // swap current element with randomly generated index swap(A, i, j); } } // main function public static void main (String[] args) { int[] A = { 1, 2, 3, 4, 5, 6 }; shuffle(A); // print the shuffled array System.out.println(Arrays.toString(A)); } } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <stdio.h> // Utility function to swap two elements A[i] and A[j] in the array void swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Function to shuffle an array A of n elements void shuffle(int A[], int n) { // read array from lowest index to highest for (int i = 0; i <= n - 2; i++) { // generate a random number j such that i <= j < n int j = i + rand() % (n - i); // swap current element with randomly generated index swap(A, i, j); } } // main function int main(void) { int A[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(A) / sizeof(A[0]); // seed for random input srand(time(NULL)); shuffle(A, n); // print the shuffled array for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.util.Arrays; import java.util.Random; class Shuffle { // Utility function to swap two elements A[i] and A[j] in the array private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Function to shuffle an array A[] public static void shuffle(int A[]) { // read array from lowest index to highest for (int i = 0; i <= A.length - 2; i++) { Random rand = new Random(); // generate a random number j such that i <= j < n int j = i + rand.nextInt(A.length - i); // swap current element with randomly generated index swap(A, i, j); } } // main function public static void main (String[] args) { int[] A = { 1, 2, 3, 4, 5, 6 }; shuffle(A); // print the shuffled array System.out.println(Arrays.toString(A)); } } |

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

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.

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.

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.

Thanks Nidhi for sharing your concerns. We can do that in C/C++, but not in Java.