# 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

# Solution

Approach 1: brute force.

Approach 2: Fisher-Yates algorithm -- for every index i from 0 to len - 1, randomly select an index j from i (inclusive, so that it can stay) to len - 1, and swap.

# Code (Python)

Approach 1:

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original_nums = [_ for _ in nums]

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        self.nums = [_ for _ in self.original_nums]
        return self.nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        nums = [_ for _ in self.nums]
        self.nums = []
        for i in range(len(nums)):
            rand_index = random.randrange(len(nums))
            self.nums.append(nums[rand_index])
            nums.pop(rand_index)
        return self.nums

Approach 2:

import random

class Solution:

    # Fisher-Yates. Idea: for every index i from 0 to len - 1, randomly select an index j from i (inclusive, so that it can stay) to len - 1, and swap
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original_nums = [_ for _ in nums]

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        self.nums = [_ for _ in self.original_nums]
        return self.nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        for i in range(len(self.nums)):
            j = random.randrange(i, len(self.nums)) # random.randrange doesn't include the second parameter
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums

# Code (C++)

Approach 1:

Approach 2: