## Description

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();


## Solutions

### 1. Backtracking

想得太复杂了啊！果然超时了！

# Time: O(nlogn)
# Space: O(n)
from random import randint
class Solution:

def __init__(self, nums: List[int]):
self.nums = nums

def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums

def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
visited = set()
permutations = []
self.dfs(visited, [], permutations)
n = len(permutations)
ran = randint(0, n-1)
print(ran)
return permutations[ran]

def dfs(self, visited, path, res):
if len(path) == len(self.nums):
res.append(path)
return

for num in self.nums:
if num in visited:
continue
self.dfs(visited, path + [num], res)
visited.remove(num)

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
# Time Limit Exceeded
# 2/10 cases passed (N/A)


### 2. 暴力搜索

删减一个备份数组的元素，用其大小作为 random 的基数，选出的值放到最后结果数组的对应位置。

class Solution:
def __init__(self, nums):
self.array = nums
self.original = list(nums)

def reset(self):
self.array = self.original
self.original = list(self.original)
return self.array

def shuffle(self):
aux = list(self.array)

for idx in range(len(self.array)):
remove_idx = random.randrange(len(aux))
self.array[idx] = aux.pop(remove_idx)

return self.array


### 3. Fisher-Yates 洗牌算法

# Time: O(n)
# Space: O(n)
from random import randint
class Solution:

def __init__(self, nums: List[int]):
self.nums = nums

def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums

def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
n = len(self.nums)
nums = self.nums[:]
for i in range(n):
j = randint(0, i)
nums[i], nums[j] = nums[j], nums[i]
return nums
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
# Time Limit Exceeded
# 2/10 cases passed (N/A)

# 10/10 cases passed (324 ms)
# Your runtime beats 64.42 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (18.1 MB)


还有基于暴力法思路的解法：

class Solution:
def __init__(self, nums):
self.array = nums
self.original = list(nums)

def reset(self):
self.array = self.original
self.original = list(self.original)
return self.array

def shuffle(self):
for i in range(len(self.array)):
swap_idx = random.randrange(i, len(self.array))
self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
return self.array