on
如何公平的洗牌
今天工作中遇到一个问题，要将数组中的元素随机的、公平的重新排列，乍一看这个问题好像还挺简单的，但实际去写代码时，发现这还是个挺有意思的问题。 因为我们不光要写出算法，而且还要从数学角度上去证明，我们的算法从理论上是符合要求的。 这个问题其实就是咱们扑克牌洗牌的问题，对于一副有54张的牌， 什么是完全随机的、公平的洗牌结果呢？应该是每一张牌在54个位置上出现的概率都是1/54。
那么如何实现每一张牌在54个位置出现的概率都是1/54呢？我们假设54张牌的牌号分别是1 2 3 … 54，并且初始状态，54张牌就是按照升序存放在54个位置。 下面我们给出一个算法，并先从理论角度，来证明它的正确性，然后再从实践的角度，来观测它是否正确。
洗牌算法
for i:=0; i<54; i++{
// 在[i, 54]区间内取随机数ri，交换位置i与位置ri的牌
}
理论证明
上面给出的算法很简单，只需要几行代码就可以实现。但这几行代码真的可以让我们得到一个公平的洗牌算法吗？下面我们从数学概率的角度来证明它的正确性。
步骤一
位置1是牌号1，我们在[1, 54]区间内取一个随机数r1，把这张牌和当前在r1位置的牌交换位置，这样能保证牌号1在54个位置出现的概率都是1/54
步骤二
对于位置2的牌，此时它的牌号有两种可能性：
- 牌号仍为2，那说明在步骤1中，牌号1取随机数r1 != 2，这个概率是53/54
- 牌号为1，那说明在步骤1中，牌号1取随机数r1 == 2，而此时牌号2就出在了位置1上，这个概率是1/54
在区间[2, 54]内取一个随机数r2，让第二张牌与r2位置的牌进行交换。此时根据咱们上面分析的那两种情况，我们可知：
- 若交换前的位置2牌号为2，那么交换后，牌号2出现在[2, 54]上任一位置的概率都是 53/54 * 1/53 = 1/54
- 若交换前的位置2牌号为1，那么交换后，牌号2仍旧在位置1上，这个概率是1/54 * 1 = 1/54
所以总体上，牌号2出现在54个位置的概率都是1/54
此时有人可能会有疑问了，第二次的交换，会对牌号1出现在54个位置的概率有影响吗？我们再全面的分析下牌号1在这两次交换的过程。
第一次交换后
牌号1在位置1的概率是1/54，在位置2的概率是1/54，在位置[3, 54]的概率是52/54
第二次交换后
- 牌号1在位置1的概率仍是1/54，因为第二次交换不会涉及位置1
- 牌号1在位置2的概率 = 53/54(第一次交换后牌号1在[2, 54]的概率) * 1/53(第二次交换时r2=牌号1所在位置的概率) = 1/54
- 牌号1在[3, 54]位置的概率 = 53/54(第一次交换后牌号1在[2, 54]的概率) * 52/53(第二次交换时r2 != 牌号1所在位置的概率) = 52/54
综上，可知第二次交换后，牌号1在54个位置的概率仍旧是1/54
步骤三
在区间[3, 54]内取一个随机数r3，让位置3的牌与r3的位置上的牌交换。
经过前两次交换，牌号3在位置1和位置2的概率都是1/54，所以牌号3仍在位置3的概率是52/54。那么进行第三次交换后牌号3出现在[3, 54]的每个位置的概率都是52/54 * 1/52 = 1/54
综上可知牌号3经过三次交换后，出现在每个位置的概率都是1/54
第三次交换后，不会影响牌号1和牌号2的概率，证明方式和步骤二中给出的方式是一样的，这里就不再详细给出证明了。
步骤i
在区间[i, 54]内取一个随机数ri，让位置i的牌与ri位置上的牌交换。重复步骤i，i++，直到i=53后结束。
实践观测
上面从理论层面证明了这个算法是完全随机、公平的。但实际上，这个算法是不是确实像我们分析的那样呢，我们还是通过程序来验证。
下面给出代码，为了方便，我们假设只有13张牌。我们进行100万次的洗牌，并且把每次洗牌的结果都记下来。通过计算每个位置上，每张牌出现的概率，来观测我们的算法是否有效。
go实现代码
package main
import (
"fmt"
"math/rand"
"time"
)
const (
cardSize = 13
shuffleCount = 10000000
)
var random *rand.Rand
func main() {
cards := [cardSize]string{"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"}
random = rand.New(rand.NewSource(time.Now().Unix()))
// 记录每个位置上，每张牌出现的次数
data := [cardSize]map[string]int{}
for i := 0; i < cardSize; i++ {
data[i] = map[string]int{"A": 0, "2": 0, "3": 0, "4": 0, "5": 0, "6": 0, "7": 0, "8": 0, "9": 0, "10": 0, "J": 0, "Q": 0, "K": 0}
}
// 模拟100万的洗牌，并累计记录每次的结果
for i := 0; i < shuffleCount; i++ {
result := shuffle(cards)
for pos, card := range result {
data[pos][card]++
}
}
printResult(cards, data)
}
// 洗牌算法
func shuffle(cards [cardSize]string) [cardSize]string {
for i := 0; i < cardSize; i++ {
r := i + random.Intn(cardSize-i)
cards[i], cards[r] = cards[r], cards[i]
}
return cards
}
func printResult(cards [cardSize]string, data [cardSize]map[string]int) {
fmt.Printf("%4s", "牌号:")
for _, card := range cards {
fmt.Printf("%7s", card)
}
fmt.Println()
for i := 0; i < cardSize; i++ {
str := fmt.Sprintf("%6s", fmt.Sprintf("位置%d: ", i+1))
for _, cnt := range data[i] {
str += fmt.Sprintf("%6.2f%%", float64(cnt*100)/float64(shuffleCount))
}
fmt.Println(str)
}
}
运行结果：
牌号: A 2 3 4 5 6 7 8 9 10 J Q K
位置1: 7.69% 7.72% 7.70% 7.66% 7.69% 7.71% 7.71% 7.68% 7.68% 7.69% 7.68% 7.69% 7.69%
位置2: 7.71% 7.72% 7.68% 7.71% 7.70% 7.68% 7.68% 7.68% 7.70% 7.69% 7.68% 7.68% 7.68%
位置3: 7.68% 7.70% 7.70% 7.69% 7.68% 7.70% 7.68% 7.73% 7.69% 7.68% 7.68% 7.69% 7.71%
位置4: 7.71% 7.69% 7.68% 7.70% 7.69% 7.70% 7.68% 7.69% 7.70% 7.67% 7.70% 7.69% 7.70%
位置5: 7.70% 7.67% 7.69% 7.68% 7.68% 7.70% 7.69% 7.67% 7.71% 7.71% 7.71% 7.68% 7.71%
位置6: 7.70% 7.67% 7.70% 7.70% 7.67% 7.71% 7.70% 7.70% 7.69% 7.70% 7.69% 7.69% 7.69%
位置7: 7.71% 7.69% 7.68% 7.69% 7.68% 7.70% 7.68% 7.70% 7.70% 7.71% 7.69% 7.69% 7.69%
位置8: 7.69% 7.72% 7.66% 7.69% 7.70% 7.68% 7.69% 7.70% 7.69% 7.67% 7.72% 7.68% 7.70%
位置9: 7.72% 7.67% 7.68% 7.70% 7.70% 7.70% 7.70% 7.67% 7.71% 7.69% 7.67% 7.70% 7.70%
位置10: 7.69% 7.68% 7.70% 7.70% 7.72% 7.68% 7.70% 7.70% 7.69% 7.68% 7.68% 7.69% 7.68%
位置11: 7.69% 7.69% 7.66% 7.68% 7.71% 7.69% 7.71% 7.69% 7.69% 7.70% 7.68% 7.73% 7.68%
位置12: 7.70% 7.71% 7.66% 7.70% 7.68% 7.68% 7.71% 7.69% 7.68% 7.69% 7.68% 7.70% 7.71%
位置13: 7.68% 7.71% 7.69% 7.67% 7.70% 7.70% 7.68% 7.69% 7.71% 7.68% 7.70% 7.68% 7.69%
理论上，每张牌出现在每个位置的概率都应该是1/13 ≈ 7.69%。从运行结果来看，我们的误差基本都在0.03%以下，这就证明了，我们的算法是正确的。
至此，我们就分别从理论和实践上，都证明了，我们给出的洗牌算法是随机、公平的。