洗牌算法（Shuffling Algorithm）

作者： /

洗牌算法（Shuffling Algorithm）是计算机科学中用于随机排列一组元素顺序的算法。它在游戏开发、数据分析、密码学等领域有着广泛应用。

1.洗牌算法概述

洗牌算法的核心目标是将一个序列中的元素随机重新排列，使得每个元素出现在每个位置的概率相等。一个良好的洗牌算法应该满足：

  1. 均匀性：所有可能的排列出现的概率相等
  2. 无偏性：算法本身不引入任何偏差
  3. 高效性：时间复杂度尽可能低
  4. Fisher-Yates洗牌算法

最经典的洗牌算法是Fisher-Yates算法，由Ronald Fisher和Frank Yates于1938年提出，后由Donald Knuth改进为现代版本。

算法步骤

  1. 从最后一个元素开始，向前遍历
  2. 对于当前位置i，随机选择一个0到i之间的整数j
  3. 交换位置i和位置j的元素
  4. 重复上述步骤直到遍历完所有元素

算法特点

• 时间复杂度：O(n)

• 空间复杂度：O(1)（原地排序）

• 保证每个排列出现的概率相同

2.Go语言中的实现

Go语言标准库在math/rand包中提供了Perm函数来生成随机排列。

2.1 rand.Perm函数

// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
func (r *Rand) Perm(n int) []int {
    m := make([]int, n)
    for i := 0; i < n; i++ {
        j := r.Intn(i + 1)
        m[i] = m[j]
        m[j] = i
    }
    return m
}

2.2 实现分析

  1. 初始化：创建一个长度为n的切片m
  2. 填充过程：
    • 对于每个位置i，随机选择一个0到i之间的位置j • 将m[j]的值赋给m[i] • 将i的值赋给m[j]
  3. 返回结果：最终得到的m就是0到n-1的一个随机排列

这种实现实际上是Fisher-Yates算法的一种变体，称为”inside-out”版本，因为它不需要预先填充数组。

2.3 使用示例

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	// 初始化随机数生成器
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	
	// 生成10个元素的随机排列
	perm := r.Perm(10)
	fmt.Println("Random permutation:", perm)
	
	// 使用排列来打乱切片
	slice := []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"}
	shuffled := make([]string, len(slice))
	for i, j := range perm {
		shuffled[i] = slice[j]
	}
	fmt.Println("Shuffled slice:", shuffled)
}

3 其他洗牌算法实现

3.1 标准Fisher-Yates实现

func FisherYatesShuffle(slice []int) {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := len(slice) - 1; i > 0; i-- {
		j := r.Intn(i + 1)
		slice[i], slice[j] = slice[j], slice[i]
	}
}

3.2 使用rand.Shuffle

Go 1.10引入了更通用的Shuffle函数：

func ShuffleSlice(slice []string) {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	r.Shuffle(len(slice), func(i, j int) {
		slice[i], slice[j] = slice[j], slice[i]
	})
}

4.算法正确性

洗牌算法的正确性证明需围绕“每个元素在所有位置出现的概率均等”

数学归纳法证明

  • 基础情形​​
    • 当数组长度为1时（n=1），元素唯一的位置概率为1/1=1，显然成立
  • ​​归纳假设​​
    • ​​假设对长度为k的数组有效，即每个元素出现在任意位置的概率为 ​​1/k​​
  • ​​递推证明​​
    • 当数组长度为k+1时：
    • ​​第k+1步操作​​：从区间 ​​[0, k]​​随机选择位置j，交换arr[k]与arr[j]
    • ​​概率分配​​：
      • ​​新元素arr[k]​​：被交换到任意位置的概率为 ​​1/(k+1)​​（因j在k+1个位置中等概率选择）
      • ​​前k个元素​​：
        • 保留在原位置的概率 = 原概率1/k × 未被替换的概率 ​​(1 – 1/(k+1))​​ = ​​k/(k+1) × 1/k = 1/(k+1)​​
        • 被替换到新位置k的概率 = ​​1/(k+1)​

蒙特卡罗实验验证（实践检验）

通过统计高频次洗牌结果的分布来近似验证概率均等性：

func TestShuffleUniformity(t *testing.T) {
	const (
		n         = 5      // 元素数量
		iterations = 10000 // 测试次数
	)
	
	// 初始化统计矩阵
	counts := make([][]int, n)
	for i := range counts {
		counts[i] = make([]int, n)
	}
	
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	
	for k := 0; k < iterations; k++ {
		perm := r.Perm(n)
		for pos, val := range perm {
			counts[val][pos]++
		}
	}
	
	// 计算每个位置的概率
	expected := float64(iterations) / float64(n)
	tolerance := 0.05 * expected // 允许5%的偏差
	
	for val := 0; val < n; val++ {
		for pos := 0; pos < n; pos++ {
			ratio := float64(counts[val][pos]) / expected
			if math.Abs(ratio-1) > tolerance {
				t.Errorf("Value %d appears in position %d %d times (%.2f%% of expected)",
					val, pos, counts[val][pos], ratio*100)
			}
		}
	}
}

5.应用场景

  • 游戏开发：卡牌游戏、随机地图生成
  • 机器学习：训练数据随机化
  • 负载均衡：请求的随机分发

滚动至顶部