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