A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 不二晨 金牌黑马   /  2018-12-18 17:10  /  2221 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

把一个数组随机打乱实质就是“洗牌问题”,洗牌问题不仅追求速度,还要求洗的足够开。
应用场景:播放器的随机播放,三国杀游戏,斗地主游戏等。

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


2 个回复

倒序浏览
奈斯
回复 使用道具 举报
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马