Knuth高效洗牌算法的示例分析

今天在做一个游戏需求的时候碰到一个问题，问题很简单，给定75个球，编号1-75，需要保证初始化的时候位置是随机的。

显然，我们可以初始化一个数组A，把75个数放进去，然后做一个shuffle函数随机交换其中的元素，这样就是随机的。

我准备这样做一个shuffle，但同时也想看看golang里面是否有这样的接口直接得到结果，看了下还真有，这个函数是rand.Perm(n)，这个函数会返回一个数组，比如我传入75，会返回一个0-74的随机数组。

arr := rand.Perm(75)

好奇心驱使我一探究竟，golang会用什么样的方式实现Perm函数呢？

打开golang的源代码，在rand.go文件中找到这个函数：

 

实现很简单，然而初一看有点懵，因为没有用到shuffle，而是一次遍历就把事情给解决了，到底是怎么回事？

仔细分析发现，这个算法非常精巧，每次遍历都是将当前的数i和已经在数组中的随机一个数m[j]进行交换，最终达到了公平随机整个数组的作用。虽然只有短短3行代码，却让人有种震撼的感觉。

顿时觉得golang很NB，确实很高效。

上面这段代码写了4行的注释，大概意思是说不能省去0那一次，看起来没啥用处，但是为了照顾r随机器中的随机序列，还是要加上，不然可能会造成负作用，这里面和随机种子以及此后随机的序列有关，为了对随机序列不产生影响保证公平性，不能省略0。

网上搜索了一下高效洗牌算法，又发现python里面也有这样的函数，这样写的：

for(int i = N - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)])         // rand(0, i) 生成 [0, i] 之间的随机整数

而这个算法的出处竟然来自于TAOCP！算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。

看似简单的问题，竟然又扯出Knuth，大意了。

能把一件小事情做到极致的人，可以称之为艺术家。Knuth名副其实。

最后以 Knuth 的一句话共勉：

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.