Come randomizzare (shuffle) un array JavaScript?

Ho una matrice come questa:

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

Come posso randomizzare / shuffle?

L’algoritmo shuffle di fatto è lo shuffle Fisher-Yates (alias Knuth).

Vedi https://github.com/coolaj86/knuth-shuffle

Puoi vedere una grande visualizzazione qui (e il post originale collegato a questo )

 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); 

Ecco un’implementazione JavaScript di Durstenfeld shuffle , una versione ottimizzata per computer di 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; } } 

L’algoritmo Fisher-Yates funziona selezionando un elemento casuale per ogni elemento dell’array originale e quindi escludendolo dall’estrazione successiva. Proprio come scegliere a caso da un mazzo di carte.

Questa esclusione viene eseguita in modo intelligente (inventato da Durstenfeld per l’uso da parte dei computer) scambiando l’elemento selezionato con l’elemento corrente e quindi selezionando l’elemento casuale successivo dal resto. Per un’efficienza ottimale, il ciclo scorre all’indietro in modo che la scelta casuale sia semplificata (può sempre iniziare da 0) e salta l’ultimo elemento perché non ci sono più altre scelte.

Il tempo di esecuzione di questo algoritmo è O (n). Si noti che lo shuffle è fatto sul posto. Quindi se non vuoi modificare l’array originale, .slice(0) prima una copia con .slice(0) .

Aggiornamento a ES6 / ECMAScript 2015

Il nuovo ES6 ci consente di assegnare due variabili contemporaneamente. Ciò è particolarmente utile quando vogliamo scambiare i valori di due variabili, dato che possiamo farlo in una riga di codice. Ecco una forma più breve della stessa funzione, utilizzando questa funzione.

 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]]; // eslint-disable-line no-param-reassign } } 

[modifica community: questa risposta non è corretta; vedere i commenti. Viene lasciato qui per riferimenti futuri perché l’idea non è così rara.]

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

Uno potrebbe (o dovrebbe) usarlo come protoipo dalla matrice:

Da 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; } 

Utilizza la libreria underscore.js. Il metodo _.shuffle() è bello per questo caso. Ecco un esempio con il metodo:

 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(); 

NUOVO!

Algoritmo shuffle Fisher-Yates più corto e probabilmente * più veloce

  1. usa mentre —
  2. bit a bit verso il basso (numeri fino a 10 cifre decimali (32 bit))
  3. rimosso chiusure inutili e altre cose

 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 } 

dimensione dello script (con fy come nome di funzione): 90bytes

DEMO http://jsfiddle.net/vvpoma8w/

* più veloce probabilmente su tutti i browser tranne Chrome.

Se hai qualche domanda basta chiedere.

MODIFICARE

sì è più veloce

PRESTAZIONI: http://jsperf.com/fyshuffle

utilizzando le funzioni più votate.

EDIT C’era un calcolo in eccesso (non serve –c + 1) e nessuno ha notato

più corto (4 byte) e più veloce (provalo!).

 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 } 

Memorizzare in cache da qualche altra parte var rnd=Math.random e quindi usare rnd() aumenterebbe anche leggermente le prestazioni sui grandi array.

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

Versione leggibile (usa la versione originale, questo è più lento, i vars sono inutili, come le chiusure & “;”, il codice stesso è anche più corto … forse leggi questo Come “ridimensionare” il codice Javascript , btw non sei in grado comprimere il seguente codice in minispinatori javascript come sopra.)

 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 } } 

Puoi farlo facilmente con la mappa e ordinare:

 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. Inseriamo ciascun elemento nell’array in un object e gli diamo una chiave di ordinamento casuale
  2. Ordiniamo usando la chiave casuale
  3. Deselezioniamo per ottenere gli oggetti originali

È ansible mischiare array polimorfici e l’ordinamento è casuale come Math.random, che è abbastanza buono per la maggior parte degli scopi.

Poiché gli elementi sono ordinati in base a chiavi coerenti che non vengono rigenerate ogni iterazione e ogni confronto viene estratto dalla stessa distribuzione, qualsiasi non casualità nella distribuzione di Math.random viene annullata.

Un modo molto semplice per i piccoli array è semplicemente questo:

 const someArray = [1, 2, 3, 4, 5]; someArray.sort(() => Math.random() - 0.5); 

Probabilmente non è molto efficiente, ma per i piccoli array funziona perfettamente. Ecco un esempio in modo da poter vedere quanto è casuale (o meno) e se si adatta al tuo caso o meno.

 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)); 
 

Randomize!

0 1 2 3 4 5 6 7 8 9

Aggiunta alla risposta @Laurens Holsts. Questo è compresso al 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 }; 
 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; }; 

Con ES2015 puoi usare questo:

 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; } 

Uso:

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

Ho trovato questa variante appesa nelle risposte “cancellate dall’autore” su un duplicato di questa domanda. A differenza di alcune delle altre risposte che hanno già molti risvolti, questo è:

  1. In realtà casuale
  2. Non sul posto (da cui il nome shuffled anziché shuffle )
  3. Non presente già qui con più varianti

Ecco un jsfiddle che lo mostra in uso .

 Array.prototype.shuffled = function() { return this.map(function(n){ return [Math.random(), n] }) .sort().map(function(n){ return n[1] }); } 

Fisher-Yates shuffle in javascript. Sto postando questo qui perché l’uso di due funzioni di utilità (swap e randInt) chiarisce l’algoritmo rispetto alle altre risposte qui.

 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); } } 

Prima di tutto, dai un’occhiata qui per un grande confronto visivo dei diversi metodi di ordinamento in javascript.

In secondo luogo, se osservi rapidamente il link sopra, scoprirai che l’ random order sembra funzionare relativamente bene rispetto agli altri metodi, pur essendo estremamente facile e veloce da implementare come mostrato di seguito:

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

Modifica : come sottolineato da @gregers, la funzione di confronto viene chiamata con valori anziché indici, motivo per cui è necessario utilizzare indexOf . Si noti che questa modifica rende il codice meno adatto per gli array più grandi quando indexOf viene eseguito nel tempo O (n).

Con ES6, 2018

Alcune delle risposte potrebbero essere abbreviate con l’ultimo ES6.

Shuffle Array Al posto

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

Con ES6 possiamo assegnare due valori contemporaneamente. Questo è particolarmente utile nella riga 4 sopra, dove due variabili sono scambiate in una riga di codice.

Lascia intatto l’array originale e restituisce un array mischiato

Se vuoi rendere una funzione più pura e lasciare intatto l’array originale, puoi semplicemente duplicare l’array e quindi eseguire lo stesso algoritmo.

 function getShuffledArray (arr){ let newArr = [...arr] 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; } 

Un Algoritmo in ascensione

L’algoritmo sottostante utilizza un ciclo ascendente. È meno intuitivo, ma breve e valido.

 function getShuffledArrayAsc (arr){ let newArr = [...arr]; 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; } 

Test di affidabilità della funzione Randomising

Le funzioni di cui sopra hanno presentato una distribuzione uniforms quando passate al "testShuffledArrayFun" di seguito, sia in Chrome che in Node. Questo è in accordo con ciò che ci aspetteremmo da una funzione randomizzante.

 function testShuffledArrayFun(getShuffledArrayFun){ // Tests the reliability of the suffleArrayFunction, by callying it 1,000 times and presenting the distribution. const testArr = [0,1,2,3,4]; const countArr = testArr.map( position => // for for each possible position in the shuffledArr, for each possible value, we'll create a counter. the counter of value 0 in position 0 will be countArr[0][0] testArr.map( value => 0) ) const n = 10000; for (var i=0 ; i {countArr[key][value]++} ); } countArr.forEach( (valueCountArr,key) => { console.log(`Position ${key}:`); valueCountArr.forEach( (count,originalValue) => { console.log(`The Value ${originalValue} appeared ${count*100/n}% `); } ); } ); } 

Una soluzione ricorsiva:

 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)); }; 

ancora un’altra implementazione di Fisher-Yates, usando la modalità strict:

 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; } 

una funzione shuffle che non cambia la matrice sorgente

Aggiornamento : qui sto suggerendo una relativamente semplice (non dalla prospettiva della complessità ) e un breve algoritmo che andrà benissimo con gli array di piccole dimensioni, ma sarà sicuramente molto più costoso dell’algoritmo classico di Durstenfeld quando si gestiscono enormi array. Puoi trovare il Durstenfeld in una delle migliori risposte a questa domanda.

Risposta originale:

Se non si desidera che la funzione shuffle muti la matrice sorgente , è ansible copiarla su una variabile locale, quindi eseguire il resto con una semplice logica di shuffling .

 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; } 

Scambio casuale: raccogliere un indice casuale, quindi aggiungere l’elemento corrispondente all’array dei risultati ed eliminarlo dalla copia dell’array sorgente . Ripeti questa azione fino a quando l’array sorgente non si svuota .

E se lo vuoi davvero breve, ecco quanto posso ottenere:

 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; } 

Solo per avere un dito nella torta. Qui presento un’implementazione ricorsiva di Fisher Yates shuffle (credo). Dà casualità uniforms.

Nota: il ~~ (doppio operatore tilde) si comporta come Math.floor() per i numeri reali positivi. È solo una scorciatoia.

 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]))); 

Though there are a number of implementations already advised but I feel we can make it shorter and easier using forEach loop, so we don’t need to worry about calculating array length and also we can safely avoid using a temporary variable.

 var arr1 = ["a", "b", "c", "d"]; arr1.forEach((val, key) => { randomIndex = Math.ceil(Math.random()*(key + 1)); arr1[key] = arr1[randomIndex]; arr1[randomIndex] = val; }); 

You can do it easily with:

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

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; } 

All the other answers are based on Math.random() which is fast but not suitable for cryptgraphic level randomization.

The below code is using the well known Fisher-Yates algorithm while utilizing Web Cryptography API for cryptographic level of randomization .

 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)); 

From a theoretical point of view, the most elegant way of doing it, in my humble opinion, is to get a single random number between 0 and n!-1 and to compute a one to one mapping from {0, 1, …, n!-1} to all permutations of (0, 1, 2, …, n-1) . As long as you can use a (pseudo-)random generator reliable enough for getting such a number without any significant bias, you have enough information in it for achieving what you want without needing several other random numbers.

When computing with IEEE754 double precision floating numbers, you can expect your random generator to provide about 15 decimals. Since you have 15!=1,307,674,368,000 (with 13 digits), you can use the following functions with arrays containing up to 15 elements and assume there will be no significant bias with arrays containing up to 14 elements. If you work on a fixed-size problem requiring to compute many times this shuffle operation, you may want to try the following code which may be faster than other codes since it uses Math.random only once (it involves several copy operations however).

The following function will not be used, but I give it anyway; it returns the index of a given permutation of (0, 1, 2, …, n-1) according to the one to one mapping used in this message (the most natural one when enumerating permuations); it is intended to work with up to 16 elements:

 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); } 

The reciprocal of the previous function (required for your own question) is below; it is intended to work with up to 16 elements; it returns the permutation of order n of (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=0; i--) { j = Math.floor(n / fact[i]); n -= j*fact[i]; q.push(p[j]); for(;j 

Now, what you want merely is:

 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]; }); } 

It should work for up to 16 elements with a little theoretical bias (though unnoticeable from a practical point of view); it can be seen as fully usable for 15 elements; with arrays containing less than 14 elements, you can safely consider there will be absolutely no bias.

A simple modification of CoolAJ86’s answer that don’t modify original array

  /** * 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 * https://stackoverflow.com/a/44071316/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; }; 
 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; } 

Randomize array using 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])); 

dimostrazione

Randomize array

  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; };