O(n) shuffling with simple proof


  • 0
    A

    Just to share another perspective and I hope it is interesting.

    Suppose that len(nums) = n.

    Algorithm:
    ○ for i in 0 ... n - 1: swap(nums[i], nums[random.randint(i, n - 1)]). # uniform sampling in the closed interval [i, n - 1]

    Proof:
    ○ To generate one sequence, there are n ways of generating the first number, n - 1 ways of generating the second number, n - 2 ways of generating the third number, ..., 1 way of generating the last number. Propability for any particular sequence is (1/n) * (1/(n - 1)) * (1/(n - 2)) * ... * 1/1 = 1/n!.
    ○ Any generated sequence must be of the same probability 1/n! In fact, we also know that there are n! possible sequences (permutations).

    Accepted implementation:

        def __init__(self, nums):
            self.nums = nums
            
        def reset(self):
            return self.nums
            
        def shuffle(self):
            shuffled = self.nums[:]
            n = len(shuffled)
            for i in range(n):
                swapIdx = random.randint(i, n - 1)
                shuffled[i], shuffled[swapIdx] = shuffled[swapIdx], shuffled[i]
            return shuffled
    

Log in to reply
 

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