Problem Explanation

The problem is asking us to create a data structure that would shuffle a provided list of integers. This data structure should have two operations:

• shuffle: It rearranges the elements in the list in a random manner. Every permutation of the list should be equally likely to be chosen.
• reset: It reverts the list back to its original state.

For instance, if we initiate the program with the list [1, 2, 3], calling the shuffle function may return [2, 1, 3], [3, 1, 2], or any other permutation of the list. Calling the reset function after that should return the original list [1, 2, 3].

Solution Approach

To solve this problem, we can use the Fisher-Yates algorithm. The basic idea of this algorithm is to iterate through the list from the last element to the first. For each element, we randomly select an index from 0 to the current index. We then swap this element with the element at the randomly selected index. This gives us a random permutation of the list.

Steps of the Algorithm:

Let's take an example of the list a = [1, 2, 3, 4, 5].

1. We start from index 4 (the last index), and generate a random index r between 0 and 4.
2. Let's say r is 2. We swap the elements at indices 4 and 2. The list becomes a = [1, 2, 5, 4, 3].
3. We move to the next index, 3, and again generate a random index r between 0 and 3.
4. Let's say r is 1. We swap the elements at indices 3 and 1. The list becomes a = [1, 4, 5, 2, 3].
5. We continue this process until we reach the first element of the list.

Solutions

Python Solution

1
2python
3import random
4
5class Solution:
6    def __init__(self, nums):
7        self.nums = nums
8        self.original = nums.copy()
9
10    def reset(self):
11        self.nums = self.original.copy()
12        return self.nums
13
14    def shuffle(self):
15        for i in range(len(self.nums) - 1, 0, -1):
16            j = random.randint(0, i)
17            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
18        return self.nums

Here, the __init__ method initializes the Solution object with a copy of the given list. The reset method reverts the list to its original state by again assigning to it the copy made during initialization. The shuffle method rearranges the list in a random manner according to the Fisher-Yates algorithm.

Java Solution

1
2java
3import java.util.Random;
4import java.util.Arrays;
5
6public class Solution {
7private int[] nums;
8private int[] original;
9
10public Solution(int[] nums) {
11    this.nums = nums;
12    this.original = nums.clone();
13}
14
15public int[] reset() {
16    this.nums = this.original;
17    this.original = original.clone();
18    return nums;
19}
20
21public int[] shuffle() {
22    Random rand = new Random();
23    for (int i = 1; i < nums.length; i++) {
24        int j = rand.nextInt(i + 1);
25        swap(nums, i, j);
26    }
27    return nums;
28}
29
30private void swap(int[] nums, int i, int j) {
31    int temp = nums[i];
32    nums[i] = nums[j];
33    nums[j] = temp;
34}
35}

This Java solution is very similar to the Python solution. We use arrays for the list of integers, and we use the clone function to copy arrays.

JavaScript Solution

1
2javascript
3class Solution {
4  constructor(nums) {
5    this.nums = nums;
6    this.original = [...nums];
7  }
8
9  reset() {
10    this.nums = [...this.original];
11    return this.nums;
12  }
13
14  shuffle() {
15    for (let i = this.nums.length - 1; i > 0; i--) {
16      let j = Math.floor(Math.random() * (i + 1));
17      [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
18    }
19    return this.nums;
20  }
21}

In JavaScript, we use the spread operator (...) to copy arrays. The rest of the code is almost the same as in the Python and Java solutions.

C++ Solution

1
2c++
3#include <vector>
4#include <random>
5
6class Solution {
7private:
8std::vector<int> nums, original;
9
10void swap(int i, int j) {
11    int temp = nums[i];
12    nums[i] = nums[j];
13    nums[j] = temp;
14}
15
16public:
17Solution(std::vector<int>& nums) : nums(nums), original(nums) {}
18
19std::vector<int> reset() {
20    nums = original;
21    return nums;
22}
23
24std::vector<int> shuffle() {
25    for (int i = nums.size() - 1; i > 0; i--) {
26        int j = rand() % (i + 1);
27        swap(i, j);
28    }
29    return nums;
30}
31};

The C++ solution is similar to the Java solution, but now we use the vector class for the list of integers.

C# Solution

1
2csharp
3
4public class Solution
5{
6private int[] nums;
7private int[] original;
8
9public Solution(int[] nums)
10{
11    this.nums = nums;
12    this.original = (int[])nums.Clone();
13}
14
15public int[] Reset()
16{
17    nums = (int[])original.Clone();
18    return nums;
19}
20
21public int[] Shuffle()
22{
23    Random rand = new Random();
24    for (int i = 0; i < nums.Length; i++)
25    {
26        int j = rand.Next(i, nums.Length);
27        int temp = nums[i];
28        nums[i] = nums[j];
29        nums[j] = temp;
30    }
31    return nums;
32}
33}

The C# solution is similar to the Java solution. The Clone method is used to copy an array to a new variable.## Kotlin Solution

1
2kotlin
3import kotlin.random.Random
4
5class Solution(nums: IntArray) {
6    private val original = nums.clone()
7    private val numsArray = nums.clone()
8
9    fun reset(): IntArray {
10        return original.clone()
11    }
12
13    fun shuffle(): IntArray {
14        for (i in numsArray.indices.reversed()) {
15            val j = Random.nextInt(i + 1)
16            val temp = numsArray[i]
17            numsArray[i] = numsArray[j]
18            numsArray[j] = temp
19        }
20        return numsArray.clone()
21    }
22}

In this Kotlin solution, the clone() function is used to copy the original array to a new variable. Like the other solutions, the algorithm follows the Fisher-Yates shuffle - but in this case, Random.nextInt(i + 1) is used to get the random index j.

Swift Solution

1
2swift
3import Foundation
4
5class Solution {
6    private let array: [Int]
7    private var shuffled: [Int]
8
9    init(_ nums: [Int]) {
10        array = nums
11        shuffled = nums
12    }
13
14    func reset() -> [Int] {
15        shuffled = array
16        return shuffled
17    }
18
19    func shuffle() -> [Int] {
20        for i in stride(from: shuffled.count - 1, through: 1, by: -1) {
21            let j = Int.random(in: 0...i)
22            shuffled.swapAt(i, j)
23        }
24        return shuffled
25    }
26}

In Swift, we use the stride(from:through:by:) method to do the reverse loop operation. Int.random(in: 0...i) is used to generate the random index j and shuffle.swapAt(i, j) is used for swapping the elements.

Typescript Solution

1
2typescript
3class Solution {
4  original:Array<number>;
5  nums:Array<number>;
6
7  constructor(nums:Array<number>) {
8      this.nums = nums;
9      this.original = [...nums];
10  }
11
12  shuffle() {
13      for (let i = this.nums.length - 1; i > 0; i--) {
14          const j = Math.floor(Math.random() * (i + 1));
15          [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
16      }
17      return this.nums;
18  }
19
20  reset() {
21      this.nums = [...this.original];
22      return this.nums;
23  }
24}
25

In this TypeScript solution, we use the spread ... operator to copy the original array to a new variable. And for similarity, Math.random() is used to create random numbers, which are then rounded down to the nearest integer using Math.floor(). For swapping the values in JS/TS, the array destructuring method is the most popular one, [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]] does that job perfectly.