avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 shuffleknuth-shuffle约瑟夫环

对于给定的 N 个数,将其公平地随机打乱,使得每个位置上每个数出现的概率相等。

约瑟夫环

遍历位置 i,每次从剩余的数中随机取一个放到该位置上。由此可以将问题归约到 不定步长约瑟夫环问题,即:N 个人围坐一圈,从 1 开始报数,每次随机一个数 x,报到 x 的人从圈中离开,然后进入下一轮游戏。因为需要求离开的顺序,所以不能使用递推法,只能用树状数组+二分,复杂度为:

  • 时间复杂度: O(N \cdot \log^2 N)
  • 额外空间复杂度: O(N)

knuth-shuffle

进一步考虑,在 shuffle 问题中,我们并不需要保证每个“人”的相对位置不变,也不必每次从上一个被踢的位置开始继续报数,而是只需要保证剩下的“人”被选出来的概率相同即可;如果能让剩下的人始终紧密地聚集到一起,那么利用数组的索引特性,每次 O(1) 即可选出该轮应该被踢出的“人”。

算法描述

  1. 从第 N 个位置(最右侧)开始向左遍历位置 i
  2. 每次从最左侧到当前位置 i 上的所有数中随机选择一个数和当前位置的数进行交换

应用上述算法,每个数字出现的概率为:

  • N 个位置上,每个数出现的概率为:\displaystyle \frac{1}{N}
  • N-1 个位置上,每个数出现的概率为:\displaystyle \frac{N-1}{N} \times \frac{1}{N-1}=\frac{1}{N}
  • ...
  • x 个位置上,每个数出现的概率为:\displaystyle \frac{N-1}{N} \times \frac{N-2}{N-1} \times \cdots \times \frac{1}{N-x}=\frac{1}{N}
  • ...

程序实现

  • 时间复杂度: O(N)
  • 额外空间复杂度: O(1)
knuth-shuffle.ts  | 9 lines.
1
2
3
4
5
6
7
8
9
export function knuthShuffle<T extends unknown = unknown>(nodes: T[]): void {
const N = nodes.length
for (let i = N - 1, j: number, x: T; i > 0; --i) {
j = Math.floor(Math.random() * (i + 1))
x = nodes[i]
nodes[i] = nodes[j]
nodes[j] = x
}
}
© 2017-2022 光和尘有花满渚、有酒盈瓯

Comments