V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
CC11001100
V2EX  ›  算法

几种洗牌算法的 Go 实现

  •  
  •   CC11001100 · 2023-02-26 00:07:30 +08:00 · 796 次点击
    这是一个创建于 397 天前的主题,其中的信息可能已经有所发展或是发生改变。

    项目地址: https://github.com/golang-infrastructure/go-shuffle

    洗牌算法( Shuffle Algorithm )

    一、支持的洗牌算法

    洗牌算法的定义:为有限集合生成随机排序的算法。

    目前支持的洗牌算法:

    • Fisher–Yates-Knuth
    • Scatology

    二、安装

    go get -u github.com/golang-infrastructure/go-shuffle
    

    三、API 代码示例

    3.1 对切片 shuffle

    package main
    
    import (
    	"fmt"
    	"github.com/golang-infrastructure/go-shuffle"
    )
    
    func main() {
    
    	// 对切片中的元素 shuffle
    	slice := []int{1, 2, 3, 4, 5}
    	shuffle.Shuffle(slice)
    	fmt.Println(slice)
    	// Output:
    	// [5 1 2 3 4]
    
    }
    

    3.2 对矩阵 shuffle

    package main
    
    import (
    	"fmt"
    	"github.com/golang-infrastructure/go-shuffle"
    )
    
    func main() {
    
    	// 对二维矩阵中的元素 shuffle
    	matrix := [][]int{
    		{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
    		{11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
    		{21, 22, 23, 24, 25, 26, 27, 28, 29, 30},
    		{31, 32, 33, 34, 35, 36, 37, 38, 39, 40},
    	}
    	// 注意可能会返回错误,比如二维数组每行长度不一致则无法 shuffle
    	err := shuffle.ShuffleMatrix(matrix)
    	if err != nil {
    		fmt.Println("Shuffle matrix failed: " + err.Error())
    		return
    	}
    	fmt.Println(matrix)
    	// Output:
    	// [[11 40 6 23 15 28 4 7 37 21] [29 26 33 5 35 13 22 32 19 34] [31 30 36 20 2 10 24 39 9 27] [16 8 18 14 1 17 38 12 25 3]]
    
    }
    

    四、Fisher–Yates-Knuth 洗牌算法

    假设现在有一个数组:

    [1, 2, 3, 4, 5]
    

    从最右边的坐标len(slice)-1开始作为right_index,每次从[0, right_index]随机选择一个下标,将选中的下标的值与right_index交换,并将right_index减一往左偏移。

    代码示例:

    // 使用自己独立的随机数生成器,与其它的调用区分开
    var standaloneRand = rand.New(rand.NewSource(time.Now().Unix()))
    
    // FisherYatesKnuthShuffle Fisher–Yates-Knuth Shuffle 或 算法对一维数组洗牌,O(n)
    func FisherYatesKnuthShuffle[T any](slice []T) {
    	for index := len(slice) - 1; index > 0; index-- {
    		chooseIndex := standaloneRand.Intn(index + 1)
    		slice[chooseIndex], slice[index] = slice[index], slice[chooseIndex]
    	}
    }
    

    我们对上面的算法扩展一下,很容易就能得到矩阵的 shuffle 算法,将矩阵的每一行看做是拼接起来的一维数组,则将对矩阵进行 shuffle 的算法转换为了对切片 shufle 的算法,而对切片进行 shuffle 我们已经实现过了,API 代码示例:

    // FisherYatesShuffleMatrix Fisher–Yates-Knuth shuffle 算法对矩阵洗牌
    func FisherYatesShuffleMatrix[T any](matrix [][]T) error {
    
    	// 参数检查
    	if err := check(matrix); err != nil {
    		return err
    	}
    
    	row, col := len(matrix), len(matrix[0])
    	for index := row*col - 1; index > 0; index-- {
    		chooseIndex := standaloneRand.Intn(index + 1)
    		matrix[index/col][index%col], matrix[chooseIndex/col][chooseIndex%col] = matrix[chooseIndex/col][chooseIndex%col], matrix[index/col][index%col]
    	}
    
    	return nil
    }
    
    // 需要保证传入的二维数据是一个矩阵,否则后面可能会越界 panic
    func check[T any](matrix [][]T) error {
    	for i := 1; i < len(matrix); i++ {
    		if len(matrix[i]) != len(matrix[i-1]) {
    			return ErrMatrixUnavailable
    		}
    	}
    	return nil
    }
    

    五、Scatology 算法

    就是在 Fisher–Yates-Knuth 的基础上随机选择的时候不再选择最右边的[0,right_index),不再展开详解。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2798 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:47 · PVG 22:47 · LAX 07:47 · JFK 10:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.