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.
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.