Thursday, 20 July 2017

Algorithms | Shuffle a given array

Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are generating the 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 randIdx 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

max = 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 of n elements (indices 0..n-1):
  for i from n - 1 down to 1 do
       j = random integer with 0 <= j <= i
       exchange array[j] and array[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);
     }
}




No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...