如何随机化(随机播放)JavaScript 数组?

我有一个像这样的数组:

var arr1 = ["a", "b", "c", "d"];

如何随机 / 随机播放?

答案

实际无偏混洗算法是 Fisher-Yates(aka Knuth)混洗。

参见https://github.com/coolaj86/knuth-shuffle

您可以在此处看到出色的可视化效果 (以及与此链接相关的原始文章)

function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);

有关使用的算法的更多信息。

这是Durstenfeld shuffle的 JavaScript 实现, Durstenfeld shuffle是 Fisher-Yates 的计算机优化版本:

/**
 * Randomize array element order in-place.
 * Using Durstenfeld shuffle algorithm.
 */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Fisher-Yates 算法的工作原理是为每个原始数组元素选择一个随机元素,然后从下一个绘制中将其排除。就像从一副纸牌中随机挑选一样。

这种排除方法是巧妙的方法(由 Durstenfeld 发明,供计算机使用),方法是将选择的元素与当前元素交换,然后从其余元素中选择下一个随机元素。为了获得最佳效率,循环会向后运行,从而简化了随机选择(它始终可以从 0 开始),并且由于没有其他选择,它会跳过最后一个元素。

该算法的运行时间为 O(n)。请注意,随机播放是就地完成的。因此,如果您不想修改原始数组,请首先使用.slice(0)对其进行复制。

更新到 ES6 / ECMAScript 2015

新的 ES6 允许我们一次分配两个变量。当我们要交换两个变量的值时,这特别方便,因为我们可以在一行代码中完成它。这是使用此功能的相同功能的缩写。

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

[社区编辑:此答案不正确;看评论。它被留在这里以备将来参考,因为这种想法并不罕见。]

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

一个人可以(或应该)将其用作 Array 的原型:

来自 ChristopheD:

Array.prototype.shuffle = function() {
  var i = this.length, j, temp;
  if ( i == 0 ) return this;
  while ( --i ) {
     j = Math.floor( Math.random() * ( i + 1 ) );
     temp = this[i];
     this[i] = this[j];
     this[j] = temp;
  }
  return this;
}

使用 underscore.js 库。在这种情况下,方法_.shuffle()很合适。这是该方法的示例:

var _ = require("underscore");

var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
  var indexOne = 0;
    var stObj = {
      '0': 0,
      '1': 1,
      '2': 2,
      '3': 3,
      '4': 4,
      '5': 5
    };
    for (var i = 0; i < 1000; i++) {
      arr = _.shuffle(arr);
      indexOne = _.indexOf(arr, 1);
      stObj[indexOne] ++;
    }
    console.log(stObj);
};
testShuffle();

您可以使用 map 和 sort 轻松完成此操作:

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((a) => ({sort: Math.random(), value: a}))
  .sort((a, b) => a.sort - b.sort)
  .map((a) => a.value)
  1. 我们将数组中的每个元素放在一个对象中,并给它一个随机的排序键
  2. 我们使用随机键排序
  3. 我们取消映射以获取原始对象

您可以对多态数组进行混洗,其排序与 Math.random 一样随机,对于大多数用途而言已经足够了。

由于元素是根据不会在每次迭代中重新生成的一致键排序的,并且每个比较都来自相同的分布,因此,Math.random 分布中的任何非随机性都会被抵消。

新!

更快或更短的 * Fisher-Yates 随机播放算法

  1. 它使用 -
  2. 按位到地板(最多 10 个十进制数字(32 位))
  3. 删除了不必要的关闭和其他内容

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}

脚本大小(以 fy 作为函数名):90bytes

演示 http://jsfiddle.net/vvpoma8w/

* 可能在除 chrome 之外的所有浏览器上都更快。

如果你有问题,就问吧。

编辑

是的,它更快

性能: http : //jsperf.com/fyshuffle

使用投票最多的功能。

编辑有一个多余的计算(不需要 --c + 1) ,没有人注意到

更短(4 字节)和更快(测试!)。

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}

缓存其他地方的var rnd=Math.random ,然后使用rnd()也会稍微提高大数组的性能。

http://jsfiddle.net/vvpoma8w/2/

可读的版本 (使用原始版本。速度较慢,vars 没用,像闭包&“;” 一样,代码本身也更短... 也许阅读此方法如何 “最小化” Javascript 代码 ,顺便说一下在类似上面的 JavaScript 缩小器中压缩以下代码。)

function fisherYates( array ){
 var count = array.length,
     randomnumber,
     temp;
 while( count ){
  randomnumber = Math.random() * count-- | 0;
  temp = array[count];
  array[count] = array[randomnumber];
  array[randomnumber] = temp
 }
}

编辑:此答案不正确

请参阅评论和https://stackoverflow.com/a/18650169/28234 。它被留在这里作为参考,因为这种想法并不罕见。


小数组的一种非常简单的方法就是:

const someArray = [1, 2, 3, 4, 5];

someArray.sort(() => Math.random() - 0.5);

这可能不是很有效,但是对于小型阵列来说,它工作得很好。这是一个示例,您可以查看它的随机性(或随机性)以及它是否适合您的用例。

const resultsEl = document.querySelector('#results');
const buttonEl = document.querySelector('#trigger');

const generateArrayAndRandomize = () => {
  const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  someArray.sort(() => Math.random() - 0.5);
  return someArray;
};

const renderResultsToDom = (results, el) => {
  el.innerHTML = results.join(' ');
};

buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));
<h1>Randomize!</h1>
<button id="trigger">Generate</button>
<p id="results">0 1 2 3 4 5 6 7 8 9</p>

可靠,高效,短

此页面上的某些解决方案不可靠(它们只能部分随机化阵列)。其他解决方案的效率大大降低。使用testShuffleArrayFun (请参见下文),我们可以测试数组改组函数的可靠性和性能。以下解决方案是:可靠,高效和简短(使用 ES6 语法)

[比较测试是使用testShuffleArrayFun与其他解决方案在 Google Chrome 中进行的]

随机排列

function getShuffledArr (array){
        for (var i = array.length - 1; i > 0; i--) {
            var rand = Math.floor(Math.random() * (i + 1));
            [array[i], array[rand]] = [array[rand], array[i]]
        }
    }

ES6 Pure,迭代式

const getShuffledArr = arr => {
        const newArr = arr.slice()
        for (let i = newArr.length - 1; i > 0; i--) {
            const rand = Math.floor(Math.random() * (i + 1));
            [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
        }
        return newArr
    };

可靠性和性能测试

如您在此页面中所见,过去这里提供了不正确的解决方案。我编写并使用以下函数来测试任何纯的(无副作用)数组随机化函数。

function testShuffleArrayFun(getShuffledArrayFun){
        const arr = [0,1,2,3,4,5,6,7,8,9]

        var countArr = arr.map(el=>{
            return arr.map(
                el=> 0
            )
        }) //   For each possible position in the shuffledArr and for 
           //   each possible value, we'll create a counter. 
        const t0 = performance.now()
        const n = 1000000
        for (var i=0 ; i<n ; i++){
            //   We'll call getShuffledArrayFun n times. 
            //   And for each iteration, we'll increment the counter. 
            var shuffledArr = getShuffledArrayFun(arr)
            shuffledArr.forEach(
                (value,key)=>{countArr[key][value]++}
            )
        }
        const t1 = performance.now()
        console.log(`Count Values in position`)
        console.table(countArr)

        const frequencyArr = countArr.map( positionArr => (
            positionArr.map(  
                count => count/n
            )
        )) 

        console.log("Frequency of value in position")
        console.table(frequencyArr)
        console.log(`total time: ${t1-t0}`)
    }

其他解决方案

其他解决方案只是为了好玩。

ES6 纯递归

const getShuffledArr = arr => {
        if (arr.length === 1) {return arr};
        const rand = Math.floor(Math.random() * arr.length);
        return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
    };

ES6 Pure 使用 array.map

function getShuffledArr (arr){
        return [...arr].map( (_, i, arrCopy) => {
            var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
            [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
            return arrCopy[i]
        })
    }

ES6 Pure 使用 array.reduce

function getShuffledArr (arr){
        return arr.reduce( 
            (newArr, _, i) => {
                var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
                [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
                return newArr
            }, [...arr]
        )
    }

编辑:此答案不正确

参见https://stackoverflow.com/a/18650169/28234 。它被留在这里作为参考,因为这种想法并不罕见。

//one line solution
shuffle = (array) => array.sort(() => Math.random() - 0.5);


//Demo
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

https://javascript.info/task/shuffle

Math.random() - 0.5是一个随机数,可以是正数或负数,因此排序功能会随机对元素进行重新排序。