题目重点：原地生成所有位置排列，重复值仍按原位置身份处理。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- randbelow(i+1)独立均匀，返回0..i整数；输出复用输入list。
- 不是按value去重随机排列；密码安全随机源需要另选，本文只讨论均匀算法。
解题路线
- 从末端i到1，均匀选当前0..i一项放到i，与原a[i]交换。固定i后以后不再改该位置。
- 给任意特定排列，末位被选概率1/n，随后条件概率1/(n−1)...，乘积1/n!。每选择序列唯一对应排列。
- 如果j总从0..n−1抽，已固定位置会被再次改，无上述证明且可能有偏。random()%range也可能有模偏差，接口必须保证均匀。
手动走一遍
n3有3×2=6条选择序列，正好六排列，每条概率1/6。空或单元素不调用随机源；重复值[A,A,B]值序列概率须合并多个位置排列，不能直接称三个值序列各1/6。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def shuffle(a,randbelow):
for i in range(len(a)-1,0,-1):
j=randbelow(i+1)
if type(j) is not int or not 0<=j<=i:raise ValueError("uniform random source out of range")
a[i],a[j]=a[j],a[i]
return a
复杂度
O(n)交换时间、O(1)额外状态，随机源成本另计；复制输入版本额外O(n)。
易错点与追问
容易失分的边界
- 每位置独立随机交换任意全数组不是标准Fisher–Yates。
- 种子重复用于并发实例可能导致相同排列，均匀证明还需随机源独立。
继续深挖
- 需要抽K个不放回样本如何只做K步部分洗牌？
- 不能修改输入时reservoir sampling适用于什么流式目标？
