洗牌算法

2021-05-19

Fisher–Yates shuffle

核心思想是从1到n之间随机取出一个数和最后一个数(n)交换，然后从1到n-1之间随机取出一个数和倒数第二个数(n-1)交换…

步骤：

    1. 写下从 1 到 N 的数字
    1. 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
    1. 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
    1. 重复第 2 步，直到所有的数字都被取出
    1. 第 3 步写出的这个序列，现在就是原始数字的随机排列

经典实现

步骤：

    1. 给定一组待混排的有限序列P
    1. 新初始化一个空的序列Q
    1. 从P中随机选取一个元素
    1. 将该元素放到序列Q的最后面，并从序列P中移除该元素
    1. 重复3-4的步骤，直到序列P中元素全部选取到了序列Q中，得到的序列Q即为一组P的混排序列

参考代码：

function shuffle(array) {
  if (!Array.isArray(array)) {
    return [];
  }
  // 初始化序列
  const result = [];

  for (let i = array.length; i > 0; i--) {
    //随机生成索引
    const idx = Math.floor(Math.random() * i);
    //将该元素加入序列
    result.push(array[idx]);
    //从数组中移除该元素
    array.splice(idx, 1);
  }
  return result;
};

流行实现

步骤：

    1. 给定一组待混排的有限序列P
    1. 从P中随机选取一个未混排的元素
    1. 将该元素与序列P的最后一个未混排的元素交换
    1. 重复2-3的步骤,直到序列P中元素全部混排过

参考代码1:

function shuffle(array) {
  if (!Array.isArray(array)) {
    return [];
  }
  for (let i = array.length; i > 0; i--) {
    //随机生成索引
    const idx = Math.floor(Math.random() * i);
    //将随机生成的元素与数组中最后一个元素交换
    if (idx !== i - 1) {
      const temp = array[idx];
      array[idx] = array[i - 1];
      array[i - 1] = temp;
    }
  }
  return array;
};

参考代码2:

/**
 * Fisher–Yates shuffle
 */
Array.prototype.shuffle = function () {
  const array = this;

  for (let i = array.length - 1; i >= 0; i--) {
    //随机生成索引
    const randomIndex = Math.floor(Math.random() * (i + 1));

    //将该元素与最后一个元素交换
    const temp = array[randomIndex];
    array[randomIndex] = array[i];
    array[i] = temp;
  }
  return array;
};

参考代码3:

Array.prototype.shuffle = function () {
  const array = this;
  let len = array.length;
  while (len) {
    //随机生成索引
    const randomIndex = Math.floor(Math.random() * len--);
    //将该元素与最后一个元素交换
    const item = array[len];
    array[len] = array[randomIndex];
    array[randomIndex] = item;
  }
  return array;
};

Lodash实现

shuffle.js

import copyArray from './.internal/copyArray.js'

/**
 * Creates an array of shuffled values, using a version of the
 * [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher-Yates_shuffle).
 *
 * @since 0.1.0
 * @category Array
 * @param {Array} array The array to shuffle.
 * @returns {Array} Returns the new shuffled array.
 * @example
 *
 * shuffle([1, 2, 3, 4])
 * // => [4, 1, 3, 2]
 */
function shuffle(array) {
  const length = array == null ? 0 : array.length
  if (!length) {
    return []
  }
  let index = -1
  const lastIndex = length - 1
  const result = copyArray(array)
  while (++index < length) {
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1))
    const value = result[rand]
    result[rand] = result[index]
    result[index] = value
  }
  return result
}

export default shuffle

.internal/copyArray.js

/**
 * Copies the values of `source` to `array`.
 *
 * @private
 * @param {Array} source The array to copy values from.
 * @param {Array} [array=[]] The array to copy values to.
 * @returns {Array} Returns `array`.
 */
function copyArray(source, array) {
  let index = -1
  const length = source.length

  array || (array = new Array(length))
  while (++index < length) {
    array[index] = source[index]
  }
  return array
}

export default copyArray

Math.random()

Math.random() 函数返回一个浮点数, 伪随机数在范围从0到小于1，也就是说，从0（包括0）往上，但是不包括1（排除1）

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

console.log(getRandomInt(3));
// expected output: 0, 1 or 2

console.log(getRandomInt(1));
// expected output: 0

console.log(Math.random());
// expected output: a number from 0 to <1

More

如何将一个 JavaScript 数组打乱顺序？
https://www.zhihu.com/question/68330851

Fisher–Yates shuffle 洗牌算法
https://gaohaoyang.github.io/2016/10/16/shuffle-algorithm/

Fisher–Yates shuffle 洗牌算法
https://www.cnblogs.com/star91/p/FisherYates-shuffle-xi-pai-suan-fa.html

Fisher–Yates shuffle
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle