Python solution using swap, O(n) for shuffle but equal possibility of getting any permutation

• ``````import random
class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type size: int
"""
self.nums = nums

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

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
nums = [i for i in range(len(self.nums))]
positions = []
for i in range(len(self.nums) - 1, -1, -1):
index = random.randint(0, i)
positions.append(nums[index])
if index != i:
nums[index] = nums[i]
return [self.nums[p] for p in positions]

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
``````

The idea is to make 0~len(nums)-1 equally possible to appear at any position. I make a list of 0~len(nums)-1 and generate random within [0,n-1], [0,n-2],... [0,0]. So every round, any position has equal possibility to get chosen. I also used the swap to fill the chosen position like in previous questions.
Finally, return nums based on my generated random positions.

• ``````import random
class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type size: int
"""
self.nums = nums

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

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
nums = [i for i in range(len(self.nums))]
for i in range(len(self.nums) - 1, -1, -1):
# choose a number to put at i
index = random.randint(0, i)
nums[i], nums[index] = nums[index], nums[i]
return [self.nums[p] for p in nums]

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
``````

Just find a fancy name and a neat implementation.
Refer: https://en.wikipedia.org/wiki/Fisherâ€“Yates_shuffle

• my version, "inside-out" algorithm:

``````import random
class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type size: int
"""
self.nums = nums

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

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
n = len(self.nums)
s = list(self.nums)
for i in range(n):
j = random.randint(0, i)
if j != i:
s[i] = s[j]
s[j] = self.nums[i]

return s
``````

• ``````import random
import itertools

class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type size: int
"""
self.nums = nums
self.size = len(nums)

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

return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
ll = itertools.permutations(self.nums)
dd = random.randint(0, self.size-1)
return list(list(ll)[dd])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.