Go中Fisher–Yates shuffle算法的使用

ivansli2021-04-192023-10-31

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: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_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 的原始版本，最初描述在 1938 年的 Ronald Fisher（上图）和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列，具体步骤如下：

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

迭代步骤演示

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

随机数取值范围	随机数	原始数据	结果
		1 2 3 4 5 6 7 8
1-8	6	1 2 3 4 5 7 8	6
1-7	2	1 7 3 4 5 8	2 6
1–6	6	1 7 3 4 5	8 2 6
1–5	1	5 7 3 4	1 8 2 6
1–4	3	5 7 4	3 1 8 2 6
1–3	3	5 7	4 3 1 8 2 6
1–2	1	7	5 4 3 1 8 2 6

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}))