Wednesday, 26 June 2019

Algorithms | Fisher-Yates shuffle Algorithm


Intuition
We can cut down the time and space complexities of shuffle with a bit of cleverness - namely, by swapping elements around within the array itself, we can avoid the linear space cost of the auxiliary array and the linear time cost of list modification.

Algorithm
  • Generate a random integer between the current index and the last index of the array.
  • Swap the elements at the current index and the chosen index.

import java.util.Arrays;
import java.util.Random;


public class ShuffleAnArray {

    private int[] nums;
    private int[] clone;
    private Random rand;

    public ShuffleAnArray(int[] nums) {
        this.nums = nums;
        this.clone = nums.clone();
        this.rand = new Random();
    }

    private void swap(int[] clone, int i, int j) {
        int temp = clone[i];
        clone[i] = clone[j];
        clone[j] = temp;
    }

    private int getRandom(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for (int i = 0; i < clone.length; i++) {
            int idx = getRandom(i, clone.length);
            swap(clone, i, idx);
        }
        return clone;
    }

    public static void main(String[] args) {
        int[] array = { 1, 2, 3 };

        ShuffleAnArray shuffleAnArray = new ShuffleAnArray(array);
        System.out.println("Array value before suffle "+Arrays.toString(shuffleAnArray.reset()));
        System.out.println("Array value before suffle "+Arrays.toString(shuffleAnArray.shuffle()));
        System.out.println("Array value after suffle "+Arrays.toString(shuffleAnArray.reset()));
    }
}

Complexity Analysis
Time complexity: O(n)
The Fisher-Yates algorithm runs in linear time, as generating a random index and swapping two values can be done in constant time.

Space complexity: O(n)
Although we managed to avoid using linear space on the auxiliary array from the brute force approach, we still need it for reset, so we're stuck with linear space complexity.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...