如何随机化（洗牌）一个JavaScript数组？
我有一个这样的数组：
var arr1 = ["a", "b", "c", "d"]; 我怎样才能随机/洗牌呢？
事实上的无偏洗牌algorithm是Fisher-Yates（又名Knuth）Shuffle。
请参阅https://github.com/coolaj86/knuth-shuffle
你可以在这里看到很棒的视觉效果 （和原来的post相关 ）
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实现，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-Yatesalgorithm通过为每个原始数组元素select一个随机元素，然后将其从下一个绘制中排除。 就像随机从一副牌中挑选。
这种排除是通过交换拾取的元素与当前元素，然后从其余元素中选取下一个随机元素，以聪明的方式完成的（由Durstenfeld发明，供计算机使用）。 为了获得最佳效率，循环向后运行，以便简化随机选取（它始终可以从0开始），并跳过最后一个元素，因为没有其他select了。
该algorithm的运行时间是O（n）。 请注意，洗牌是在原地完成的。 所以如果你不想修改原始数组，首先用.slice(0)复制它。
更新到ES6 / ECMAScript 2015
新的ES6允许我们一次分配两个variables。 当我们想交换两个variables的值时，这是特别方便的，因为我们可以在一行代码中完成。 这是使用此function的相同function的简短forms。
function shuffleArray(array) { for (let i = array.length - 1; i > 0; i--) { let 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();
新！
较短和可能*更快的Fisher-Yates shufflealgorithm
- 它使用时—
- 按位到底（数字最多10个十进制数字（32位））
- 删除了不必要的closures和其他东西
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作为函数名）：90字节
DEMO http://jsfiddle.net/vvpoma8w/
*除了Chrome之外，所有的浏览器可能都会更快。
如果你有任何问题，只要问。
编辑
是的，这是更快
性能： http : //jsperf.com/fyshuffle
使用顶级投票function。
编辑有一个计算过量（不需要 – C + 1） ，没有人注意到
更短（4字节）和更快（testing！）。
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 }
在其他地方cachingvar rnd=Math.random ，然后使用rnd()也会稍微增加大数组的性能。
http://jsfiddle.net/vvpoma8w/2/
可读版本 （使用原来的版本，这是慢的，variables是没用的，就像closures＆“;”，代码本身也更短…可能读这个如何'minify'的Javascript代码 ，顺便说一句，你不能压缩下面的代码在一个像上面那样的javascript minifiers中。）
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 } }
添加到@Laurens霍尔斯答案。 这是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 };
小数组的一个非常简单的方法就是这样：
const someArray = [1, 2, 3, 4, 5]; someArray.sort(() => Math.random() * 2 - 1);
这可能不是很有效，但对于小型arrays，这工作得很好:)
var shuffle = function(array) { temp = []; for (var i = 0; i < array.length ; i++) { temp.push(array.splice(Math.floor(Math.random()*array.length),1)); } return temp; };
有了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();
我发现这个变体挂在“作者删除”的答案上，这个问题的重复。 不像其他一些已经有很多upvotes的答案，这是：
- 其实是随意的
- 不是就地（因此
shuffled而不是shuffle） - 这里还没有多个变种
这里有一个jsfiddle显示它在使用中 。
Array.prototype.shuffled = function() { return this.map(function(n){ return [Math.random(), n] }) .sort().map(function(n){ return n[1] }); }
Fisher-Yates在javascript中洗牌。 我在这里发布这个，因为使用两个实用函数（交换和randInt）澄清algorithm相比，在这里的其他答案。
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中的不同sorting方法的伟大的视觉比较。
其次，如果您快速查看上面的链接，您会发现random ordersorting与其他方法相比performance得相对较好，而实现起来非常简单快捷，如下所示：
function shuffle(array) { var random = array.map(Math.random); array.sort(function(a, b) { return random[array.indexOf(a)] - random[array.indexOf(b)]; }); }
编辑 ：正如@gregers指出的，比较函数是用值而不是索引来调用的，这就是为什么你需要使用indexOf 。 请注意，由于indexOf在O（n）时间运行，因此此更改使代码不太适合较大的数组。
基于Fisher-Yates Shuffle ，你可以试试这个可重用的数组shuffle组件 。 例：
shuffle([1, 2, 3, 4, 5]) // => [2, 4, 1, 5, 3]
我也喜欢这个Lodash函数返回一个新的数组，并保持原来的数组不变：
function shuffle(array) { var rand, index = -1, length = array.length, result = Array(length); while (++index < length) { rand = Math.floor(Math.random() * (index + 1)); result[index] = result[rand]; result[rand] = array[index]; } return result; }
（正确的披露：我在CoCycles团队。）
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; }
recursion解决scheme：
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)); };
你可以用地图和sorting轻松完成：
let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}] let shuffled = ary .map((a) => ({sort: Math.random(), value: a})) .sort((a, b) => a.sort > b.sort ? 1 : -1) .map((a) => a.value)
忽略这个。 它不会像预期的那样提供随机性。 http://codepen.io/GottZ/pen/ZbEaZg
.sort(function () { return [1, -1, 0][Math.random() *3 |0]; });
规范说只使用1，-1和0代表更高，更低和相等的价值。
取决于数组正在sorting。
通过提供随机值，数组将基本上被随机sorting。
Array.prototype.sort()后面的algorithm只是检查正数，负数和相等数。 是的，有人可以使用Math.random() * 0.5但严重的是，平等也应该是随机的。
CoolAJ86 答案的简单修改，不修改原始数组
/** * Returns a new array whose contents are a copy shuffled of the array. * @param {Array} a items to shuffle. * https://stackoverflow.com/a/2450976/1673761 */ const shuffle = (array) => { let currentIndex = array.length; let temporaryValue; let randomIndex; const newArray = array.slice(); // While there remain elements to shuffle... while (currentIndex) { randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // And swap it with the current element. temporaryValue = newArray[currentIndex]; newArray[currentIndex] = newArray[randomIndex]; newArray[randomIndex] = temporaryValue; } return newArray; };
有些答案可以用最新的ES6缩短。
无序播放arrays
function shuffleArray (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允许我们一次分配两个值。 在上面第4行中，这是非常方便的，其中两个variables在一行代码中交换。
保持原始数组完好，并返回一个混洗数组
如果你想做一个更纯的函数，并保持原始数组完好，你可以简单地复制数组，然后运行相同的algorithm。
function getShuffledArray (arr){ let newArr = arr.slice(); for (var i = newArr.length - 1; i > 0; i--) { var rand = Math.floor(Math.random() * (i + 1)); [newArr[i], newArr[rand]]=[newArr[rand], newArr[i]]; } return newArr; }
递增algorithm
下面的algorithm使用一个上升循环。 它不那么直观，但又短而有效。
function getShuffledArray (arr){ let newArr = arr.slice(); for (let i = 1; i < newArr.length ; i++) { const rand = Math.floor( Math.random() * (i + 1) ); [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]]; } return newArr; }
testing随机函数的可靠性
我用下面的函数来testing随机函数的可靠性。 这个函数打印出每个位置的值的分布。
function testShuffledArrayFun(getShuffledArrayFun){ let arr = [0,1,2,3,4]; var length = arr.length; var countArr = [] // for for each possible position in the shuffledArr, for each possible value, we'll create a counter. the counter of element 0 in position 0 will be countArr[0][0] for (var i=0 ; i<length ; i++){ let positionArr= []; for (var j=0 ; j<length ; j++){ positionArr.push(0); // Set Counter To 0 } countArr.push(positionArr); } const n = 10000; for (var i=0 ; i<n ; i++){ // We'll call getShuffledArrayFun for n times. And for each time we'll increment the counter. At the end we'll print the results so we can verify that the function actually randomises the array. var shuffledArr = getShuffledArrayFun(arr); shuffledArr.forEach( (value, key) => {countArr[key][value]++} ); } countArr.forEach( (positionArr,key) => { console.log(`Position ${key}:`); positionArr.forEach( (count,originalValue) => { console.log(`The Value ${originalValue} appeared ${count*100/n}% `); } ); } ); }
在chrome和node中都运行getShuffledArray函数的testing，在控制台中显示均匀分布。 这与我们期望的随机化function是一致的。
所有其他的答案都是基于Math.random（），它是快速的，但不适合用于密码学级别的随机化。
下面的代码使用众所周知的Fisher-Yatesalgorithm，同时利用Web Cryptography API进行encryption级别的随机化 。
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));
Fisher-Yates的这种变化稍微有效一些，因为它避免了将元素与自身交换：
function shuffle(array) { var elementsRemaining = array.length, temp, randomIndex; while (elementsRemaining > 1) { randomIndex = Math.floor(Math.random() * elementsRemaining--); if (randomIndex != elementsRemaining) { temp = array[elementsRemaining]; array[elementsRemaining] = array[randomIndex]; array[randomIndex] = temp; } } return array; }
Array.prototype.shuffle=function(){ var len = this.length,temp,i while(len){ i=Math.random()*len-- |0; temp=this[len],this[len]=this[i],this[i]=temp; } return this; }
使用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]));
演示
随机化数组
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;
var shuffledArray = function(inpArr){ //inpArr - is input array var arrRand = []; //this will give shuffled array var arrTempInd = []; // to store shuffled indexes var max = inpArr.length; var min = 0; var tempInd; var i = 0; do{ //generate random index between range tempInd = Math.floor(Math.random() * (max - min)); //check if index is already available in array to avoid repetition if(arrTempInd.indexOf(tempInd)<0){ //push character at random index arrRand[i] = inpArr[tempInd]; //push random indexes arrTempInd.push(tempInd); i++; } } // check if random array length is equal to input array length while(arrTempInd.length < max){ return arrRand; // this will return shuffled Array } };
Just pass the array to function and in return get the shuffled array
Considering apply it to in loco or to a new immutable array, following other solutions, here is a suggested implementation:
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; };
Ronald Fisher and Frank Yates shuffle
ES2015 (ES6) release
Array.prototype.shuffle2 = function () { this.forEach( function (v, i, a) { let j = Math.floor(Math.random() * (i + 1)); [a[i], a[j]] = [a[j], a[i]]; } ); return this; }
Jet optimized ES2015 (ES6) release
Array.prototype.shuffle3 = function () { var m = this.length; while (m) { let i = Math.floor(Math.random() * m--); [this[m], this[i]] = [this[i], this[m]]; } return this; }
the shortest arrayShuffle function
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; }
I see no one has yet given a solution that can be concatenated while not extending the Array prototype (which is a bad practice ). Using the slightly lesser known reduce() we can easily do shuffling in a way that allows for concatenation:
var randomsquares = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle).map(n => n*n);
You'd probably want to pass the second parameter [] , as otherwise if you try to do this on an empty array it'd fail:
// Both work. The second one wouldn't have worked as the one above var randomsquares = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle, []).map(n => n*n); var randomsquares = [].reduce(shuffle, []).map(n => n*n);
Let's define shuffle as:
var shuffle = (rand, one, i, orig) => { if (i !== 1) return rand; // Randomize it only once (arr.length > 1) // You could use here other random algorithm if you wanted for (let i = orig.length; i; i--) { let j = Math.floor(Math.random() * i); [orig[i - 1], orig[j]] = [orig[j], orig[i - 1]]; } return orig; }
You can see it in action in JSFiddle or here:
var shuffle = (all, one, i, orig) => { if (i !== 1) return all; // You could use here other random algorithm here for (let i = orig.length; i; i--) { let j = Math.floor(Math.random() * i); [orig[i - 1], orig[j]] = [orig[j], orig[i - 1]]; } return orig; } for (var i = 0; i < 5; i++) { var randomarray = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle, []); console.log(JSON.stringify(randomarray)); }
