import random

def reservior_sampling(n, k):
    """
    表示有 n 个数，随机采样 k 个
    """
    nums = [i for i in range(1, n + 1)]

    res = []
    for i in range(k):
        # 前K个数字可以直接填充
        res.append(nums[i])
    
    for i in range(k, len(nums)):
        # 假设 i == k (也是说这是 第 k + 1个元素), 那么 该数字有  k / (k + 1) 的概率被选中去去换
        replace_idx = random.randint(0, i)
        if replace_idx < k:
            res[replace_idx] = nums[i]
    return res

pool = reservior_sampling(100, 10)
print(pool)
# [78, 52, 41, 84, 66, 43, 25, 71, 45, 24]