如何生成一个无重复的随机数序列？

直接回答

生成无重复随机序列的核心思路是：先构造一个包含所有目标元素的有序序列，再做随机打乱，即 Fisher-Yates 洗牌算法。另一种思路是从候选集合中随机抽取并移除已选元素。前者时间 O(n)、结果均匀，是最标准的做法。

展开解析

Fisher-Yates 从后往前遍历数组，每次将位置 i 与 [0, i] 区间内的随机位置 j 交换。关键在于随机下标范围必须包含 i 本身，且从后往前（或等价的从前往后变体），否则某些排列概率不均。易错点是每次都在整个数组范围里取随机位置，那样不是均匀洗牌。若只需从 0..n-1 中抽 m 个不重复数（m << n），可用哈希集合存已选值、冲突重抽，期望 O(m)；也可用部分洗牌：只做前 m 次交换后取前 m 个。追问方向：如何证明均匀性（每个排列概率 1/n!）、如何用蓄水池采样处理流式数据。

示例

import random

def shuffled(n):
    arr = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]
    return arr