我有一个这样的数组:

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

我如何随机化/打乱它?


当前回答

这是一个Durstenfeld shuffle的JavaScript实现,这是Fisher Yates的优化版本:

/* Randomize array 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;
    }
}

它为每个原始数组元素选择一个随机元素,并将其排除在下一次抽奖中,就像从一副牌中随机选择一样。

这种巧妙的排除将拾取的元素与当前元素交换,然后从剩余元素中拾取下一个随机元素,向后循环以获得最佳效率,确保简化随机拾取(始终可以从0开始),从而跳过最终元素。

算法运行时间为O(n)。请注意,洗牌是在适当的位置完成的,因此如果您不想修改原始数组,请首先使用.sslice(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].reduce((a,x,i)=>{a.splice(Math.floor(Math.random()*(i+1)),0,x);return a},[])

变量ia=[1,2,3];var it=1000;var f=(a,x,i)=>{a.splice(Math.floor(Math.random()*(i+1)),0,x);返回a};var a=新数组(it).fill(ia).map(x=>x.reduce(f,[]));var r=新数组(ia.length).fill(0).map((x,i)=>a.reduce((i2,x2)=>x2[i]+i2,0)/it)console.log(“这些值应该相当相等:”,r);

事实上的无偏洗牌算法是Fisher Yates(又名Knuth)shuffle。

你可以在这里看到一个很棒的可视化效果(以及链接到此的原始帖子)

函数洗牌(数组){let currentIndex=array.length,randomIndex;//而还有一些元素需要洗牌。while(currentIndex!=0){//拾取剩余的元素。randomIndex=数学地板(Math.random()*当前索引);当前索引--;//并将其与当前元素交换。[array[currentIndex],array[randomIndex]]=[array[randomIndex],array[currentIndex]];}返回数组;}//如此使用var arr=[2,11,37,42];洗牌(arr);控制台日志(arr);

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

使用array.splice()随机化数组

function shuffleArray(array) {
   var temp = [];
   var len=array.length;
   while(len){
      temp.push(array.splice(Math.floor(Math.random()*array.length),1)[0]);
      len--;
   }
   return temp;
}
//console.log("Here >>> "+shuffleArray([4,2,3,5,8,1,0]));

demo

从理论的角度来看,在我看来,最优雅的方法是得到一个介于0和n之间的随机数-并计算从{0,1,…,n!-1}到(0,1、2,…,n-1)的所有置换的一对一映射。只要你能使用一个足够可靠的(伪)随机发生器来获得这样一个数字而没有任何明显的偏差,你就有足够的信息来实现你想要的,而不需要其他几个随机数。

当使用IEEE754双精度浮点数计算时,您可以期望随机生成器提供大约15个小数。既然你有15岁=1307674368000(带13位数字),您可以对最多包含15个元素的数组使用以下函数,并假设最多包含14个元素的阵列不会有明显的偏差。如果您正在处理一个固定大小的问题,需要多次计算该洗牌操作,您可能需要尝试以下代码,因为它只使用Math.random一次(但它涉及多次复制操作),因此可能比其他代码更快。

下面的函数不会被使用,但我还是给出了它;它根据此消息中使用的一对一映射(枚举排列时最自然的映射)返回给定排列(0,1,2,…,n-1)的索引;它打算与多达16个元件一起工作:

function permIndex(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var tail = [];
    var i;
    if (p.length == 0) return 0;
    for(i=1;i<(p.length);i++) {
        if (p[i] > p[0]) tail.push(p[i]-1);
        else tail.push(p[i]);
    }
    return p[0] * fact[p.length-1] + permIndex(tail);
}

上一个函数的倒数(您自己的问题需要)如下:;它打算与多达16个元件一起工作;它返回(0,1,2,…,s-1)的n阶排列:

function permNth(n, s) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var i, j;
    var p = [];
    var q = [];
    for(i=0;i<s;i++) p.push(i);
    for(i=s-1; i>=0; i--) {
        j = Math.floor(n / fact[i]);
        n -= j*fact[i];
        q.push(p[j]);
        for(;j<i;j++) p[j]=p[j+1];
    }
    return q;
}

现在,你想要的只是:

function shuffle(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000];
    return permNth(Math.floor(Math.random()*fact[p.length]), p.length).map(
            function(i) { return p[i]; });
}

它应该适用于多达16个元素,但有一点理论偏差(尽管从实际角度看不明显);它可以被视为完全可用于15个元件;对于包含少于14个元素的数组,您可以放心地认为绝对没有偏差。

考虑将其应用于本地或新的不可变数组,遵循其他解决方案,以下是建议的实现:

Array.prototype.shuffle = function(local){
  var a = this;
  var newArray = typeof local === "boolean" && local ? this : [];
  for (var i = 0, newIdx, curr, next; i < a.length; i++){
    newIdx = Math.floor(Math.random()*i);
    curr = a[i];
    next = a[newIdx];
    newArray[i] = next;
    newArray[newIdx] = curr;
  }
  return newArray;
};