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

2020/09/17 17:31 · javascript ·  · 0评论

我有一个像这样的数组:

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

如何随机/随机播放?

实际无偏混洗算法是Fisher-Yates(又名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];
shuffle(arr);
console.log(arr);

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

这是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)请注意,随机播放是就地完成的,因此,如果您不想修改原始数组,请先使用复制它.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();
});

您可以使用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分布中的任何非随机性都将被抵消。

速度

时间复杂度为O(N log N),与快速排序相同。空间复杂度为O(N)。这不像Fischer Yates混洗那样有效,但是在我看来,代码明显更短且功能更多。如果阵列很大,则一定要使用Fischer Yates。如果您的阵列很小,只有几百个项目,则可以这样做。

一个人可以(或应该)将其用作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();

新!

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

  1. 它使用while-
  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
 }
}

随机排列

    function shuffleArr (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
    };

可靠性和性能测试

此页面上的某些解决方案不可靠(它们只能部分随机化阵列)。其他解决方案的效率明显较低。借助testShuffleArrayFun(见下文),我们可以测试阵列混洗功能的可靠性和性能。

    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它被留在这里作为参考,因为这种想法并不罕见。


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

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>

添加到@Laurens Holsts答案。这是50%压缩的。

function shuffleArray(d) {
  for (var c = d.length - 1; c > 0; c--) {
    var b = Math.floor(Math.random() * (c + 1));
    var a = d[c];
    d[c] = d[b];
    d[b] = a;
  }
  return d
};

编辑:此答案不正确

参见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 是一个可能为正数或为负数的随机数,因此排序功能会随机对元素进行重新排序。

借助ES2015,您可以使用以下一种:

Array.prototype.shuffle = function() {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]]
  }
  return this;
}

用法:

[1, 2, 3, 4, 5, 6, 7].shuffle();

这是最简单的一种

function shuffle(array) {
  return array.sort(() => Math.random() - 0.5);
}

进一步的例子,你可以在这里检查

我在此问题的副本中的“作者删除”答案中发现了这种变体。与已经有许多投票的其他一些答案不同,这是:

  1. 其实随机
  2. 不到位(因此,shuffled名称而不是shuffle
  3. 这里尚不存在多种变体

这是一个使用中的jsfiddle

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}
var shuffle = function(array) {
   temp = [];
   originalLength = array.length;
   for (var i = 0; i < originalLength; i++) {
     temp.push(array.splice(Math.floor(Math.random()*array.length),1));
   }
   return temp;
};
arr1.sort(() => Math.random() - 0.5);

您可以轻松地做到这一点:

// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);

请参考JavaScript排序数组

递归解决方案:

function shuffle(a,b){
    return a.length==0?b:function(c){
        return shuffle(a,(b||[]).concat(c));
    }(a.splice(Math.floor(Math.random()*a.length),1));
};

Fisher-Yates在javascript中随机播放。我将其发布在这里是因为与此处的其他答案相比,使用两个实用程序功能(交换和randInt)使算法更清晰。

function swap(arr, i, j) { 
  // swaps two elements of an array in place
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function randInt(max) { 
  // returns random integer between 0 and max-1 inclusive.
  return Math.floor(Math.random()*max);
}
function shuffle(arr) {
  // For each slot in the array (starting at the end), 
  // pick an element randomly from the unplaced elements and
  // place it in the slot, exchanging places with the 
  // element in the slot. 
  for(var slot = arr.length - 1; slot > 0; slot--){
    var element = randInt(slot+1);
    swap(arr, element, slot);
  }
}

首先,在这里查看一下javascript中不同排序方法的视觉效果。

其次,如果快速浏览一下上面的链接,您会发现random order与其他方法相比,该排序似乎表现相对较好,并且实现起来非常容易和快捷,如下所示:

function shuffle(array) {
  var random = array.map(Math.random);
  array.sort(function(a, b) {
    return random[array.indexOf(a)] - random[array.indexOf(b)];
  });
}

编辑:正如@gregers所指出的,compare函数是使用值而不是索引来调用的,这就是为什么需要使用indexOf请注意,此更改使代码indexOf在O(n)时间内运行时不太适合较大的数组

不改变源数组的随机播放功能

更新:在这里,我建议一个相对简单的算法(不是从复杂性的角度来看),并且简短的算法对小型数组也可以,但是当处理大型数组时,它的成本肯定会比经典的Durstenfeld算法高得多您可以在对此问题的最高答复之一中找到Durstenfeld

原始答案:

如果您不希望 shuffle函数更改源数组,可以将其复制到局部变量,然后使用简单的shuffle 逻辑进行其余操作

function shuffle(array) {
  var result = [], source = array.concat([]);

  while (source.length) {
    let index = Math.floor(Math.random() * source.length);
    result.push(source[index]);
    source.splice(index, 1);
  }

  return result;
}

改组逻辑:选择一个随机索引,然后将相应的元素添加到结果数组,并将其从源数组副本中删除重复此操作,直到源数组变

如果您真的想简短一点,这是我能走多远:

function shuffle(array) {
  var result = [], source = array.concat([]);

  while (source.length) {
    let index = Math.floor(Math.random() * source.length);
    result.push(source.splice(index, 1)[0]);
  }

  return result;
}

使用严格模式的Fisher-Yates的另一个实现:

function shuffleArray(a) {
    "use strict";
    var i, t, j;
    for (i = a.length - 1; i > 0; i -= 1) {
        t = a[i];
        j = Math.floor(Math.random() * (i + 1));
        a[i] = a[j];
        a[j] = t;
    }
    return a;
}

所有其他答案都是基于Math.random()的,该方法速度很快,但不适用于加密级别的随机化。

在下面的代码是使用公知的Fisher-Yates,同时利用算法Web Cryptography API随机化的加密级

var d = [1,2,3,4,5,6,7,8,9,10];

function shuffle(a) {
	var x, t, r = new Uint32Array(1);
	for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {
		crypto.getRandomValues(r);
		x = Math.floor(r / 65536 / 65536 * m) + i;
		t = a [i], a [i] = a [x], a [x] = t;
	}

	return a;
}

console.log(shuffle(d));

使用ES6功能的现代短内联解决方案:

['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);

(出于教育目的)

对CoolAJ86 答案的简单修改,不会修改原始数组:

 /**
 * Returns a new array whose contents are a shuffled copy of the original array.
 * @param {Array} The items to shuffle.
 * https://stackoverflow.com/a/2450976/1673761
 * https://stackoverflow.com/a/44071316/1673761
 */
const shuffle = (array) => {
  let currentIndex = array.length;
  let temporaryValue;
  let randomIndex;
  const newArray = array.slice();
  // While there remains elements to shuffle...
  while (currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    // Swap it with the current element.
    temporaryValue = newArray[currentIndex];
    newArray[currentIndex] = newArray[randomIndex];
    newArray[randomIndex] = temporaryValue;
  }
  return newArray;
};

尽管已经建议了许多实现,但是我觉得我们可以使用forEach循环使它更短,更容易,因此我们不必担心计算数组长度,并且可以安全地避免使用临时变量。

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

myArr.forEach((val, key) => {
  randomIndex = Math.ceil(Math.random()*(key + 1));
  myArr[key] = myArr[randomIndex];
  myArr[randomIndex] = val;
});
// see the values
console.log('Shuffled Array: ', myArr)

只是为了指责派。在这里,我提出了Fisher Yates shuffle的递归实现(我认为)。它给出统一的随机性。

注意:(~~双波浪号运算符)实际上的行为类似于Math.floor()正实数。只是一个捷径。

var shuffle = a => a.length ? a.splice(~~(Math.random()*a.length),1).concat(shuffle(a))
                            : a;

console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));

编辑:上面的代码是O(n ^ 2)的使用,.splice()但是我们可以通过交换技巧消除O(n)中的拼接和混洗。

var shuffle = (a, l = a.length, r = ~~(Math.random()*l)) => l ? ([a[r],a[l-1]] = [a[l-1],a[r]], shuffle(a, l-1))
                                                              : a;

var arr = Array.from({length:3000}, (_,i) => i);
console.time("shuffle");
shuffle(arr);
console.timeEnd("shuffle");

问题是,JS无法配合大型递归。在这种特殊情况下,根据您的浏览器引擎和一些未知事实,您将数组大小限制在3000〜7000之间。

随机数组

 var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
 var n = arr.length; var tempArr = [];

 for ( var i = 0; i < n-1; i++ ) {

    // The following line removes one random element from arr 
     // and pushes it onto tempArr 
     tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
 }

 // Push the remaining item onto tempArr 
 tempArr.push(arr[0]); 
 arr=tempArr; 

最短的arrayShuffle功能

function arrayShuffle(o) {
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
}

从理论的角度来看,我拙见认为,最优雅的方法是获得0n!-1之间单个随机数,并计算从到的所有排列的一对一映射只要您可以使用足够可靠的(伪)随机数生成器来获得这样一个数字而没有任何明显的偏差,您就可以在其中拥有足够的信息来实现所需的信息,而无需其他几个随机数。{0, 1, …, n!-1}(0, 1, 2, …, n-1)

使用IEEE754双精度浮点数进行计算时,可以期望随机生成器提供约15个小数。由于您有15!= 1,307,674,368,000(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个元素;它返回n顺序排列(0, 1, 2, …, s-1)

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个元素的数组,您可以放心地认为绝对不会有偏差。

本文地址:http://javascript.askforanswer.com/ruhesuijihuasuijibofangjavascriptshuzu.html
文章标签: ,   ,   ,  
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!