fisher_yates_knuth_shuffle.go

package shuffle

import (
	"math/rand"
	"time"
)

// 使用自己独立的随机数生成器，与其它的调用区分开
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]
	}
}

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