# O(n) shuffling with simple proof

• 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
``````

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