🔖 shuffleknuth-shuffle约瑟夫环

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

约瑟夫环

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

  • 时间复杂度： O(N⋅log2⁡N)
  • 额外空间复杂度： O(N)

knuth-shuffle

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

算法描述

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

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

  • 第 N 个位置上，每个数出现的概率为：1N
  • 第 N−1 个位置上，每个数出现的概率为：N−1N×1N−1=1N
  • ...
  • 第 x 个位置上，每个数出现的概率为：N−1N×N−2N−1×⋯×1N−x=1N
  • ...

程序实现

  • 时间复杂度： 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-2025 光和尘有花满渚、有酒盈瓯

Comments