资讯专栏INFORMATION COLUMN

洗牌算法

omgdog / 2635人阅读

摘要:描述拷贝数组从扫描数组,选择一个随机数新数组的新数组的新数组的原始数组重复第步,直到末尾最终的新数组就是随机的参考三种洗牌算法

洗牌算法 Fisher-Yates Shuffle

Fisher–Yates 随机置乱算法,通俗说就是生成一个有限集合的随机排列。

描述:

写下从 1 到 N 的数字

取一个从 1 到剩下的数字(包括这个数字)的随机数 k

从低位开始,得到第 k 个还没有被取出的数字,把它写在独立的一个列表的最后一位

重复第 2 步,直到所有的数字都被取出

第 3 步写出的这个序列,现在就是原始数字的随机排列

function getRandom(arr, length) {
  const random = Math.floor(Math.random() * length)

  // 原始算法将在此处消耗较多资源
  if (arr.includes(random)) {
    return getRandom(arr, length)
  } else {
    return random
  }
}

function randomArray(arr) {
  let newArr = []
  const length = arr.length
  let index = length - 1
  let indexArr = []
  while (index >= 0) {
    const random = getRandom(indexArr, length)
    indexArr.push(random)
    newArr.push(arr[random])
    --index
  }

  return newArr
}
Knuth-Durstenfeld Shuffle

Knuth 和  Durstenfeld   在 Fisher 等人的基础上对算法进行了改进,不借助新的组数,直接在原地交换。该算法的基本思想和 Fisher 类似,每次从未处理的数据中随机取出一个数,并和最后一个剩余元素交换,然后剩余元素的数量减一。

function randomArray(arr) {
  const length = arr.length
  for (let index = length - 1; index > 0; index--) {
    const random = Math.floor(Math.random() * index)
    const temp = arr[index]
    arr[index] = arr[random]
    arr[random] = temp
  }

  return arr
}
Inside-Out Algorithm

Inside-Out Algorithm 算法的思想是从前往后,借助旧数组,将新数组中位置 k 和位置 i 的数字进行交互

描述

拷贝数组

从 i(0 - N)扫描数组,选择一个随机数 k( 0 <= k <= i)

新数组的[i] = 新数组的[k], 新数组的[k] = 原始数组[i]

重复第 2 步,直到末尾

最终的新数组就是随机的

function randomArray(arr) {
  let newArr = arr.concat([])
  const length = arr.length
  for (let index = 0; index < length; index++) {
    const random = Math.floor(Math.random() * (index + 1))
    newArr[index] = newArr[random]
    newArr[random] = arr[index]
  }

  return newArr
}
参考

三种洗牌算法 shuffle

Fisher–Yates shuffle From Wikipedia

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/104294.html

相关文章

  • 随机问题之洗牌算法

    摘要:百度文库洗牌算法提到一种换牌思路随机交换两个位置,共交换次,越大,越接近随机。洗牌插牌法优化版,可以用数学归纳法证明,这种洗牌是均匀的。每次生成一张最大的牌,与随机的某张牌换位子抽牌抽牌优化换牌插牌插牌优化文章转载自随机问题之洗牌算法 洗牌算法是我们常见的随机问题,在玩游戏、随机排序时经常会碰到。它可以抽象成这样一个问题。 得到一个M以内的所有自然数的随机顺序数组。 在百度搜洗牌算法,...

    instein 评论0 收藏0
  • 数组随机排序:洗牌算法(Fisher–Yates shuffle)

    摘要:代码实现代码一测试用例输出其中,代码二测试用例输出其中,参考资料洗牌算法学习笔记数组随机排序洗牌算法给数组随机排序洗牌算法原理 原理及步骤 1.定义一个数组(shuffled),长度(length)是原数组(arr)长度2.取 0 到 index (初始0) 随机值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...

    张金宝 评论0 收藏0
  • 程序员的算法趣题Q50: 完美洗牌

    摘要:的结果与原书的结果不符。上一篇程序员的算法趣题欲速则不达程序员的算法趣题欲速则不达下一篇程序员的算法趣题同时结束的沙漏本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述  2. 解题分析 2.1 思路1 2.2 思路2 3. 代码及测试 4....

    xeblog 评论0 收藏0
  • Underscore 源码(三)随机洗牌算法

    摘要:随机洗牌算法说实话,以前理解数组的排序,都是将数组按照一定的逻辑由大到小或者由小到大排序,我自己是没有碰到过随机打乱数组排序的问题。然后里用的是所谓的洗牌算法,很高效。总结又是三个知识点,分别是随机洗牌分组和函数的实现,没什么复杂的。 这是第三篇关于 Underscore 的源码解读,最近一段时间学的东西很少,自己太忙了,一方面忙着找实习,晚上回去还要写毕业论文。毕业论文真的很忧伤,因...

    silencezwm 评论0 收藏0
  • js 数组随机数 数组洗牌

    摘要:首先通过数组调用是令系统随机选取大于等于且小于的伪随机值进入到函数后分别定义了变量和变量为当前数组的长度,先声明,以便在下面中使用。循环一圈后就形成了对数组的洗牌。 这次分享一个随机数组洗牌的一个算法,让你得到随机数组。 假如1个数组的值是这样的: const arr = [a, b, c, d, e, f, g]; 因为在实践操作中,在网上搜可以搜到一大堆随机的这些代码。但是实际上究...

    jay_tian 评论0 收藏0

发表评论

0条评论

omgdog

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<