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.
1import random
2
3class Solution:
4 def __init__(self, nums: List[int]):
5 self.original = nums[:]
6 self.array = nums[:]
7
8 def reset(self) -> List[int]:
9 self.array = self.original[:]
10 return self.array
11
12 def shuffle(self) -> List[int]:
13 for i in range(len(self.array) - 1, 0, -1):
14 j = random.randint(0, i)
15 self.array[i], self.array[j] = self.array[j], self.array[i]
16 return self.array
17The Python implementation uses list slicing to copy arrays. The 'shuffle' function deploys Fisher-Yates algorithm by swapping the current index element with a randomly selected index element. The 'reset' function simply returns a fresh slice of the original.
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.
1class Solution {
2 constructor(nums)
In JavaScript, this solution uses recursion to generate permutations, not fully efficient nor strictly generating permutations but a form of randomized shuffle which is recursive, ensuring all elements are possibly swapped.