Wednesday, 4 October 2017

Algorithms | Shuffle a given array

Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function random() that generates random number in O(1) time. The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.

Array starts off with 11 elements initialized to array[n] = n, maxIdx starts off at 10:
0
1
2
3
4
5
6
7
8
9
10

At each iteration, a random number r is selected between 0 and maxIdx, array[randIdx] and array[maxIdx] are swapped, the new array[maxIdx] is returned, and maxIdx is decremented:

maxIdx = 10, randIdx = 3
0
1
2
10
4
5
6
7
8
9
3

maxIdx = 9, randIdx = 7
0
1
2
10
4
5
6
9
8
7
3

maxIdx = 8, randIdx = 1
0
8
2
10
4
5
6
9
1
7
3

maxIdx = 7, randIdx = 5
0
8
2
10
4
9
6
5
1
7
3

After 11 iterations, all numbers in the array have been selected, maxIdx == 0, and the array elements are shuffled. At this point, maxIdx can be reset to 10 and the process can continue.

Detailed algorithm
To shuffle an array a of n elements (indices 0..n-1):
  for i from n - 1 down to 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

Code to shuffle an array
package com.algorithmforum.rand;
import java.util.Random;
public class RandomGenerator {

            /** This function to generate a random permutation of array[]*/
            private static void randomize (int array[]) {
                        int n = array.length;
                        /*
                         * Start from the last element and swap one by one.
                         * We don't need to run for the first element that's why i> 0
                         */
                        for (int i = n-1; i > 0; i--) {
                                    /** Pick a random index from 0 to i.*/
                                    Random rand = new Random();
                                    int value = rand.nextInt(50);
                                    int j = value % (i+1);

                                    /** Swap array[i] with the element at random index. */
                                    swap(i, j, array);
                        }
            }

            /** A utility function to swap to integers. **/
            private static void swap (int i, int j, int[] array) {
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
            }

            /** This is an utility function to print an array. */
            private static void printArray (int array[]) {
                        for (int i:array) {
                                    System.out.print(i+" ");
                        }
                        System.out.println();
            }
           
            public static void main(String[] args) {
                        int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

                        randomize(arr);
                       
                        printArray(arr);
            }
}


Related Posts Plugin for WordPress, Blogger...