随机置乱与蓄水池抽样

A. 两种方法：

• 给每张牌分配独立随机实数后排序（$O(n\log n)$）。
• Knuth/Fisher–Yates 洗牌（$O(n)$）：

for(i=1; i<=n; i++)
  swap(A[i],A[Random(i,n)]);

B. 蓄水池抽样（reservoir sampling，容量 1）：

• 先选第 1 个字符；
• 读到第 $k$ 个字符时，以概率 $1/k$ 用它替换当前选择。

最终每个字符被选中的概率都是 $1/m$。

Original Explanation

AnswerA:

• Sort approach: assign each card a random real $\in(0,1)$, then sort => $O(n\log n)$.
• Knuth shuffle: $O(n)$

for(i=1; i<=n; i++)
   swap(A[i],A[Random(i,n)]);

AnswerB:
Pick the first char, then for the 2nd char keep old with prob 1/2, else new. For the 3rd keep old with prob 2/3, else new, etc. Each char has $1/m$ chance.