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]
- I'm not sure if I am allowed to use the built in random library, nor the point of this question.
- I am neither sure if this can be done in a O(1) space, as
resetfunction requires remembering the original state of the array.
- The reason I'm keeping
self.ordis that initializing a large
rangeis very time consuming, so initializing it over and over again will fail the test, exceeding the time limit.
ordertakes less memory than keeping a copy of the original array, as the original array may contain objects larger that
I'm open to suggestions. Thank you for reading.
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:
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.
@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.
@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 :)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.