Fisher–Yates shuffle

每次从后往前等概率抽取一个下标index(0~i),然后交换该index与下标i的值
时间复杂度: O(n)
空间复杂度: O(1)
缺点:会打乱原数组,且是从后往前计算,因此不适用于动态变化的数组**
证明:
设目标元素为i

1. 第一次才抽中i的概率为1/n
2. 第二次才抽中i的概率为 (n-1)/n * 1/(n-1) = 1/n
   因此任意位置,任意元素的抽中概率均为1/n

import random
def shuffle(nums):    
    for i in range(len(nums)-1, -1, -1):        
        j = random.randint(0, i)        
        nums[i], nums[j] = nums[j], nums[i]

蓄水池抽样

特点：如果数据集合的量特别大或者还在增长（相当于未知数据集合总量），该算法依然可以等概率抽样
证明：
设目标抽取数为m，而 i 为目标数，分两种情况讨论:

1. i为在<=m时进入的池子，且最后留在池子的概率：

当池子未满时，进入池子的概率为1。当池子满，即m+1之后，每次加入新值但没有替换到的概率分别为(m/m+1),(m+1/m+2)…，N次的时候为(N-1/N)，因此最后总概率为:

1. i为在>m时进入的池子，且最后留在池子的概率：

当池子已经满了，进入池子的概率为m/i，后面每次不被替换的概率为:(1- 1/i+1), (1- 1/i+2)…. (1- 1/n),因此最后的总概率为:

…(1-*%5Cfrac%7B1%7D%7Bn%7D)%20%3D%20%5Cfrac%7Bm%7D%7Bn%7D#card=math&code=%5Cfrac%7Bm%7D%7Bi%7D%2A%281-%5Cfrac%7B1%7D%7Bi%2B1%7D%29%2A…%2A%281-%2A%5Cfrac%7B1%7D%7Bn%7D%29%20%3D%20%5Cfrac%7Bm%7D%7Bn%7D&id=7c4617d5)

import random
def pool_shuffle(nums):
    M = 10 # 假设只取样10个
    res = []
    count_times = 0
    for num in nums:
        count_times += 1
        if count_times > M:
            rand_index = random.randint(0, count_times)
            if rand_index <= M:
                res[rand_index-1] = num
        else:
            res.append(num)
    return res
nums = []
for i in range(100000):
    nums.append(i)
print(pool_shuffle(nums))