Straight-forward Python Solution


  • 2
    W
    from random import shuffle
    class Solution(object):
    
        def __init__(self, nums):
            """
            
            :type nums: List[int]
            :type size: int
            """
            self.nums = nums
            self.l = len(nums)
            self.ord = range(self.l)
    
        def reset(self):
            """
            Resets the array to its original configuration and return it.
            :rtype: List[int]
            """
            self.ord = range(self.l)
            return self.nums
    
        def shuffle(self):
            """
            Returns a random shuffling of the array.
            :rtype: List[int]
            """
            shuffle(self.ord)
            return [self.nums[i] for i in self.ord]
    
    1. I'm not sure if I am allowed to use the built in random library, nor the point of this question.
    2. I am neither sure if this can be done in a O(1) space, as reset function requires remembering the original state of the array.
    3. The reason I'm keeping self.ord is that initializing a large range is very time consuming, so initializing it over and over again will fail the test, exceeding the time limit.
    4. Remembering order takes less memory than keeping a copy of the original array, as the original array may contain objects larger that int.

    I'm open to suggestions. Thank you for reading.


  • 0
    W

    I think it is okay to use built-in library, but random.shuffle() in Python does not really generate equally likely permutations. In Python 2.7 doc, it says the following:
    random.shuffle(x[, random])
    Shuffle the sequence x in place. The optional argument random is a 0-argument function returning a random float in [0.0, 1.0); by default, this is the function random().
    Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.


  • 0

    @WKVictor True, but that applies to pretty much every solution. So I suggest you bring it up as a topic on its own, not just as a comment under this particular solution.


  • 0
    W

    @StefanPochmann Thanks for your suggestion. I put it as a new topic and also add a figure to show the unbiasedness of Fisher-Yates shuffle :)


Log in to reply
 

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