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


  • 0
    P
    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.


  • 0
    P
    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


  • 0

    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
    

  • 0
    L
    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])
    

Log in to reply
 

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