带权重的 random()

random() 是一个重要的函数，它会以相同的概率返回一个随机数。带权重的 random() 要求我们生成具有不同权重的随机数。

例如：A = [10, 50, 20, 20]，如果我们用 P(x) 表示返回 x 的概率，则有：
P(0) = 10 / 100 = 0.1
P(1) = 50 / 100 = 0.5
P(2) = 20 / 100 = 0.2
P(3) = 20 / 100 = 0.2

一种简单的方法是我们可以创建一个包含 个元素的数组。我们随机设置 个元素为 ， 个元素为 ， 个元素为 ， 个元素为 。
然后我们可以从 到 随机选择一个索引，并返回所选索引上的值。然而，上述方法有一个明显的缺点。它会消耗大量内存，设置值也会花费大量时间。

我们能否压缩这些信息，而不是创建一个数组？答案是可以的，让我们考虑大小为 的权重数组 的前缀和数组 （0索引）。

然后对于给定的数组，我们有 和 。我们可以从 中提取 个区间 。每个区间对应于权重长度。这意味着，如果我们随机选择一个索引 , 落入 的概率是.

import random
import bisect


class Solution:
    def __init__(self, w):
        self.prefix = []          # 前缀和数组
        s = 0
        for weight in w:
            self.prefix.append(s)
            s += weight
        self.sw = s               # 总权重

    def pick_index(self):
        number = random.randrange(self.sw)
        # 找到 number 落入的区间下标（等价于 Java 的 TreeMap.floorKey）
        return bisect.bisect_right(self.prefix, number) - 1

---

洗牌算法

Fisher–Yates 洗牌算法可用于生成数组的随机排列。该算法背后的原理是我们需要确保每对索引，即 具有相同的交换概率。

import random


def shuffle(arr):
    n = len(arr)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)        # j ∈ [0, i]，含 i
        arr[i], arr[j] = arr[j], arr[i]
    return arr

在上述实现中，对于每个 ，我们随机选择一个 进行交换。

注意，我们也包括 ，因为有可能我们根本不改变它。

通过这种方式，我们能够覆盖所有对 ，并且当我们从 到 迭代 i 时，我们将能够覆盖所有对。