题目重点：NG 电面给牌列表要求洗牌；逐位从剩余下标均匀选择并交换，推导每种排列 1/n! 与边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版返回新列表，原列表不变；若面试要求原地修改，可去掉复制。
- 随机源对 0..m−1 等概率，不能用随机排序键代替无偏洗牌。
解题路线
- 复制输入；对 i=0..n−2，从闭区间 [i,n−1] 均匀选 j，交换 a[i],a[j]。
- 不变量：前 i 项已固定且在所有尚未选的牌中等概率抽取；每种最终排列概率 1/n×1/(n−1)×…×1=1/n!。
- 随机数 API 要避免上界误解，确保尾位置也可能被选；空/单牌直接返回。
- 可注入随机源做可重复单测，另对小 n 穷举所有随机选择路径验证每排列出现一次。
手动走一遍
牌 [A,B,C]：第一位 3 种选择，第二位从剩下 2 种中选，最后一位确定，共 3×2=6 条等概率路径，对应全部 6 种排列。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from random import randrange
def shuffled(cards, pick_index=randrange):
"""Return a shuffled copy; pick_index(n) is uniform in [0,n)."""
result = list(cards)
for i in range(len(result) - 1):
offset = pick_index(len(result) - i)
j = i + offset
result[i], result[j] = result[j], result[i]
return result
复杂度
O(n) 时间、返回副本 O(n) 空间；原地版额外 O(1)。随机源质量不由算法本身保证。
易错点与追问
容易失分的边界
- 每次从全数组重新随机选而允许已固定位置被选。
- 把 random sort key 当作严格均匀排列。
- 随机整数上界少取一项。
- 只测输出仍是同一组牌，未测分布。
继续深挖
- 如何证明均匀？
- 牌组大到内存放不下怎么办？
- 需要密码学安全随机时改什么？
