We usually use random.shuffle() to get a random list in python, now we search which algorithm use in this function

Source Code

   def shuffle(self, x, random=None):
        """Shuffle list x in place, and return None.

        Optional argument random is a 0-argument function returning a
        random float in [0.0, 1.0); if it is the default None, the
        standard random.random will be used.

        """

        if random is None:
            randbelow = self._randbelow
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]
        else:
            _int = int
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = _int(random() * (i+1))
                x[i], x[j] = x[j], x[i]

Fisher-Yates Shuffle

Time complexity: O(n) Space complexity: O(n)

Proof of randomness

Prove that the i-th position where each element is placed in the new array is 1 / n.

Proof:

The probability that an element m is placed in the i-th position P = the probability that m is not selected when the first i-1 positions select elements * the probability that m is selected in the i-th position,

\begin{aligned} p = \frac{n-1}{n}\times \frac{n-1}{n} … \frac{n-i+1}{n-i+2} \times \frac{1}{n-i+1} \end{aligned}

Initialize the original array and the new array, the length of the original array is n (known);
From the unprocessed array (if there are i left), randomly generate a number p between [0, i) (assuming the array starts from 0);
Take out the p-th number from the remaining i-numbers;
Repeat steps 2 and 3 until all numbers have been taken;
The sequence of numbers taken from step 3 is a scrambled sequence.

Fisher-Yates Shuffle

时间复杂度: O(n) 空间复杂度: O(n)

   def shuffle(self, x, random=None):
        """Shuffle list x in place, and return None.
        将列表x随机排序，然后返回None。

        Optional argument random is a 0-argument function returning a
        random float in [0.0, 1.0); if it is the default None, the
        standard random.random will be used.
        可选参数random是一个0参数的函数，返回一个
         [0.0，1.0）中的随机浮点数； 如果是默认值None，则
         将使用标准random.random。

        """

        if random is None:
            randbelow = self._randbelow
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                # 选择数组x [：i + 1]中与x [i]交换的元素

                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]
        else:
            _int = int
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                # 选择数组x [：i + 1]中与x [i]交换的元素

                j = _int(random() * (i+1))
                x[i], x[j] = x[j], x[i]

随机性证明

证明每个元素被放置在新数组中的第i个位置是1/n。

证明：

一个元素m被放入第i个位置的概率 P = 前i-1个位置选择元素时没有选中m的概率 * 第i个位置选中m的概率，即：

\begin{aligned} p = \frac{n-1}{n}\times \frac{n-1}{n} … \frac{n-i+1}{n-i+2} \times \frac{1}{n-i+1} \end{aligned}

原理

初始化原始数组和新数组，原始数组长度为n(已知)；
从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）；
从剩下的k个数中把第p个数取出；
重复步骤2和3直到数字全部取完；
从步骤3取出的数字序列便是一个打乱了的数列。