Sponsored
The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient algorithm for generating a random permutation of a finite sequence. The algorithm works by iterating backward through the array and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet.
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
1class Solution {
2 constructor(nums) {
3 this.original = nums.slice();
4 this.array = nums.slice();
5 }
6
7 reset() {
8 this.array = this.original.slice();
9 return this.array;
10 }
11
12 shuffle() {
13 for (let i = this.array.length - 1; i > 0; i--) {
14 let j = Math.floor(Math.random() * (i + 1));
15 [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
16 }
17 return this.array;
18 }
19}In JavaScript, 'slice()' is used to copy the array. The 'shuffle' method uses the Fisher-Yates algorithm to swap elements randomly. The 'reset' simply returns a fresh copy of the original array.
This approach involves generating a permutation recursively by picking an element and placing it at different positions. This is less efficient than the Fisher-Yates method and not suitable for large arrays.
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
1from random import randint
2
3class Solution:
In this Python solution, we recursively generate a permutation by swapping the current element with any element after it. This ensures that all permutations are equally probable, though it's less efficient for large arrays compared to Fisher-Yates.