Go对Fisher–Yates shuffle算法的实现

Golang中rand.Shuffle

从go1.10开始，math包新增了rand.Shuffle方法。

 data := []int{1,2,3,4,5,6,7,8}

rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(data), func(i, j int) {
data[i], data[j] = data[j], data[i]
})

fmt.Println(data)
// [1 2 6 4 5 3 7 8] or other,每次执行结果都不一样

通过，该方法可以实现随机打散功能（一般用于切片、数组）。

rand.Shuffle 源码

 // Shuffle pseudo-randomizes the order of elements using the default Source.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }


// Shuffle pseudo-randomizes the order of elements.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func (r *Rand) Shuffle(n int, swap func(i, j int)) {
if n < 0 {
panic("invalid argument to Shuffle")
}

  // 可以看到，这里使用了 Fisher–Yates shuffle 洗牌算法
// Fisher-Yates shuffle: 
// Shuffle really ought not be called with n that doesn't fit in 32 bits.
// Not only will it take a very long time, but with 2³¹! possible permutations,
// there's no way that any PRNG can have a big enough internal state to
// generate even a minuscule percentage of the possible permutations.
// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
i := n - 1
for ; i > 1<<31-1-1; i-- {
j := int(r.Int63n(int64(i + 1)))
swap(i, j)
}
for ; i > 0; i-- {
j := int(r.int31n(int32(i + 1)))
swap(i, j)
}
}

通过源码以及注释发现，其实现使用了 Fisher–Yates shuffle 洗牌算法。

那么，问题来了：什么是Fisher–Yates shuffle 洗牌算法？

Fisher–Yates shuffle 洗牌算法

简单来说 Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。这个算法生成的随机排列是等概率的，同时这个算法非常高效。

Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher（上图）和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列，具体步骤如下：

写下从 1 到 N 的数字
取一个从 1 到剩下的数字（包括这个数字）的随机数 k
从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
重复第 2 步，直到所有的数字都被取出
第 3 步写出的这个序列，现在就是原始数字的随机排列

迭代步骤演示

根据每次迭代次数可以用下面的表格，描述这个算法的执行过程

Go对Fisher–Yates shuffle算法的实现

 rand.Seed(time.Now().UnixNano())

shuffle := func(in []int) []int {
// i等于len(in) - 1, 即：最后一个位置下标
// 循环条件：i>0是因为i等于0时，只剩下最后一个元素了。这个时候们已经不需要再进行位置交换了
for i := len(in) - 1; i > 0; i-- {
// 获取 [0, i) 之间的随机数，即：随机得到的位置
rands := rand.Intn(i + 1)
      
  // 把随机位置的数值放到最后一位，然后继续下一轮，从[0, i-1) 找随机
in[i], in[rands] = in[rands], in[i]
}
return in
}

fmt.Println(shuffle([]int{1,2,3,4,5,6,7,8}))

时间复杂度

在每次迭代时交换这个被取出的数字到原始列表的最后，时间复杂度为 O(n)。

总结

Fisher–Yates shuffle 算法是一个非常高效又公平的随机排序算法，如果有随机排序数组的需求，可以使用这个算法。
时间复杂度仅为 O(n)
逻辑简单、易于理解

参考

Fisher–Yates shuffle 洗牌算法