Shuffle an array [Fisher - Yates algorithm]

XXX. Fisher-Yates Shuffle Algorithm

Math

Randomization

Problem Statement:

Implement the Fisher-Yates Shuffle algorithm to shuffle an array of integers randomly. The solution should include the ability to reset the array to its original configuration and shuffle it multiple times.

Algorithm:

1. Initialize two arrays: one to store the original array and another to perform operations.
2. To shuffle the array:
   • Iterate through the array and swap each element with a randomly chosen element from its current index to the end of the array.
3. To reset the array:
   • Return a copy of the original array.

Complexity:

Time Complexity: O(n) for shuffling and O(1) for reset.
Space Complexity: O(n) for storing the original and working arrays.

Java Implementation:

// Fisher-Yates Shuffle Algorithm
class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

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

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

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }

    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }

    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) 
            swap(i, randRange(i, array.length));
        return array;
    }
}
                

Python Implementation:

import random

class Solution:
    def __init__(self, nums):
        self.array = nums
        self.original = nums[:]

    def reset(self):
        self.array = self.original[:]
        return self.original

    def shuffle(self):
        for i in range(len(self.array)):
            swap_idx = random.randint(i, len(self.array) - 1)
            self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
        return self.array
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

class Solution {
private:
    vector array;
    vector original;

    int randRange(int min, int max) {
        return rand() % (max - min) + min;
    }

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

public:
    Solution(vector& nums) {
        array = nums;
        original = nums;
        srand(time(0));
    }

    vector reset() {
        array = original;
        return original;
    }

    vector shuffle() {
        for (int i = 0; i < array.size(); i++) {
            swap(i, randRange(i, array.size()));
        }
        return array;
    }
};