把一个数组随机打乱实质就是“洗牌问题”,洗牌问题不仅追求速度,还要求洗的足够开。
应用场景:播放器的随机播放,三国杀游戏,斗地主游戏等。
Fisher-Yates随机置乱算法
也称高纳德置乱算法,该算法是无偏的,所以每个排列都是等可能的。以数字1~8为例,具体步骤如下图所示:
从1~8中随机抽取一个数,例如随机数是3,那么交换第8位和第三位的数字。
此时数组顺序为12456783,重复第一步,从1~7中抽取一个数字,假设为4,那么交换第7位和第4位的数字。
依次类推,直到第一个位置也被替代。
代码演示:
package main
import (
"errors"
"fmt"
"time"
"math/rand"
)
func init() {
rand.Seed(time.Now().Unix())
}
func main() {
strs := []string{
"1", "2", "3", "4", "5", "6", "7", "8",
}
a, _ := Random(strs, 3)
fmt.Println(a)
}
func Random(strings []string, length int) (string, error) {
if len(strings) <= 0 {
return "", errors.New("the length of the parameter strings should not be less than 0")
}
if length <= 0 || len(strings) <= length {
return "", errors.New("the size of the parameter length illegal")
}
for i := len(strings) - 1; i > 0; i-- {
num := rand.Intn(i + 1)
strings, strings[num] = strings[num], strings
}
str := ""
for i := 0; i < length; i++ {
str += strings
}
return str, nil
}
无论在算法本身的执行过程中,还是生成随机数的过程,使用Fisher-Yates洗牌算法必须小心,否则就可能出现一些偏差。例如随机数生成带来的误差,造成洗牌的结果整体上不满足均匀分布的特点。
---------------------
【转载】仅作分享,侵删
作者:benben_2015
原文:https://blog.csdn.net/benben_2015/article/details/79996849
|
|