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.
1using System;
2
3public class Solution {
4 private int[] original;
5 private int[] array;
6 private Random rand;
7
8 public Solution(int[] nums) {
9 original = (int[])nums.Clone();
10 array = (int[])nums.Clone();
11 rand = new Random();
12 }
13
14 public int[] Reset() {
15 array = (int[])original.Clone();
16 return array;
17 }
18
19 public int[] Shuffle() {
20 for (int i = array.Length - 1; i > 0; i--) {
21 int j = rand.Next(i + 1);
22 int temp = array[i];
23 array[i] = array[j];
24 array[j] = temp;
25 }
26 return array;
27 }
28}In C#, we make use of 'Array.Clone()' to copy arrays. 'Shuffle' employs the Fisher-Yates algorithm by randomizing within the bounds of the current index. 'Reset' restores the array to its original configuration.
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.