Hoe een JavaScript-array randomiseren (shufflen)?

Ik heb een array als deze:

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

Hoe kan ik het willekeurig verdelen/shufflen?


Antwoord 1, autoriteit 100%

Het feitelijke onpartijdige shuffle-algoritme is de Fisher-Yates (ook bekend als Knuth) Shuffle.

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

Je kunt een geweldige visualisatie hierzien (en het originele bericht hieraan gekoppeld)

function shuffle(array) {
  var currentIndex = array.length,  randomIndex;
  // While there remain elements to shuffle...
  while (0 !== currentIndex) {
    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;
    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
      array[randomIndex], array[currentIndex]];
  }
  return array;
}
// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

Antwoord 2, autoriteit 50%

Hier is een JavaScript-implementatie van de Durstenfeld shuffle, een geoptimaliseerde versie van 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;
    }
}

Het kiest een willekeurig element voor elk origineel array-element en sluit het uit van de volgende trekking, zoals willekeurig kiezen uit een pak kaarten.

Deze slimme uitsluiting verwisselt het gekozen element met het huidige element en kiest vervolgens het volgende willekeurige element uit de rest, achteruit in een lus voor optimale efficiëntie, zodat de willekeurige selectie wordt vereenvoudigd (deze kan altijd bij 0 beginnen), en daardoor de laatste element.

De runtime van het algoritme is O(n). Merk opdat de shuffle ter plaatse wordt gedaan, dus als u de originele array niet wilt wijzigen, maakt u er eerst een kopie van met .slice(0).


BEWERKEN:Updaten naar ES6 / ECMAScript 2015

Met de nieuwe ES6 kunnen we twee variabelen tegelijk toewijzen. Dit is vooral handig als we de waarden van twee variabelen willen omwisselen, omdat we dit in één regel code kunnen doen. Hier is een kortere vorm van dezelfde functie, die deze functie gebruikt.

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

Antwoord 3, autoriteit 9%

Waarschuwing!
Het gebruik van dit algoritme wordt niet aanbevolen, omdat het inefficiënten sterk bevooroordeeldis; zie Reacties. Het wordt hier achtergelaten voor toekomstig gebruik, omdat het idee niet zo zeldzaam is.

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

Deze https://javascript.info/array-methods#shuffle-an-array tutorial legt de verschillen duidelijk uit.


Antwoord 4, autoriteit 7%

Je kunt het gemakkelijk doen met kaart en sorteren:

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]
let shuffled = unshuffled
  .map((value) => ({ value, sort: Math.random() }))
  .sort((a, b) => a.sort - b.sort)
  .map(({ value }) => value)
  1. We plaatsen elk element in de array in een object en geven het een willekeurige sorteersleutel
  2. We sorteren met behulp van de willekeurige sleutel
  3. We maken de kaart los om de originele objecten te krijgen

Je kunt polymorfe arrays in willekeurige volgorde afspelen en de sortering is net zo willekeurig als Math.random, wat goed genoeg is voor de meeste doeleinden.

Aangezien de elementen worden gesorteerd op consistente sleutels die niet elke iteratie opnieuw worden gegenereerd, en elke vergelijking uit dezelfde distributie trekt, wordt elke niet-willekeurigheid in de distributie van Math.random opgeheven.

Snelheid

Tijdcomplexiteit is O(N log N), hetzelfde als snel sorteren. Ruimtecomplexiteit is O(N). Dit is niet zo efficiënt als een Fischer Yates-shuffle, maar naar mijn mening is de code aanzienlijk korter en functioneler. Als je een grote array hebt, moet je zeker Fischer Yates gebruiken. Als je een kleine array hebt met een paar honderd items, zou je dit kunnen doen.


Antwoord 5, autoriteit 4%

Je zou het kunnen (of moeten) gebruiken als een prototype van Array:

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

Antwoord 6, autoriteit 4%

Gebruik de underscore.js-bibliotheek. De methode _.shuffle()is in dit geval goed.
Hier is een voorbeeld met de methode:

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

Antwoord 7, autoriteit 3%

NIEUW!

Korter & waarschijnlijk *sneller Fisher-Yates shuffle-algoritme

  1. het gebruikt while—
  2. bitsgewijs naar verdieping (getallen tot 10 cijfers achter de komma (32-bits))
  3. onnodige sluitingen verwijderd & andere dingen

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
}

scriptgrootte (met fy als functienaam): 90bytes

DEMO
http://jsfiddle.net/vvpoma8w/

*sneller waarschijnlijk in alle browsers behalve chrome.

Als je vragen hebt, stel ze dan gewoon.

BEWERKEN

ja, het is sneller

PRESTATIES:http://jsperf.com/fyshuffle

met behulp van de meest gestemde functies.

BEWERKEN
Er was een teveel aan berekening (niet nodig –c+1) en niemand merkte het

korter(4bytes)&sneller(test het!).

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
}

Het ergens anders cachen van var rnd=Math.randomen vervolgens rnd()gebruiken, zou de prestaties op grote arrays ook iets verhogen.

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

Leesbare versie(gebruik de originele versie. Dit is langzamer, vars zijn nutteloos, zoals de sluitingen & “;”, de code zelf is ook korter … lees dit misschien Javascript-code ‘verkleinen’, je kunt het volgende trouwens niet comprimeren code in een javascript-verkleiner zoals de bovenstaande.)

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

Antwoord 8, autoriteit 3%

Shuffle-array op zijn plaats

   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 puur, iteratief

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

Betrouwbaarheids- en prestatietest

Sommige oplossingen op deze pagina zijn niet betrouwbaar (ze maken de array slechts gedeeltelijk willekeurig). Andere oplossingen zijn beduidend minder efficiënt. Met testShuffleArrayFun(zie hieronder) kunnen we array-shuffling-functies testen op betrouwbaarheid en prestaties.

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

Andere oplossingen

Andere oplossingen voor de lol.

ES6 puur, recursief

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

Antwoord 9, autoriteit 2%

Bewerken: dit antwoord is onjuist

Zie opmerkingen en https://stackoverflow.com/a/18650169/28234. Het wordt hier achtergelaten ter referentie omdat het idee niet zeldzaam is.


Een heel eenvoudige manier voor kleine arrays is gewoon deze:

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

Het is waarschijnlijk niet erg efficiënt, maar voor kleine arrays werkt dit prima. Hier is een voorbeeld, zodat u kunt zien hoe willekeurig (of niet) het is en of het bij uw gebruik past of niet.

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>

Antwoord 10

Toevoegen aan @Laurens Holsts antwoord. Dit is 50% gecomprimeerd.

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

Antwoord 11

Met ES2015 kun je deze gebruiken:

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

Gebruik:

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

Antwoord 12

//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.5is een willekeurig getal dat positief of . kan zijn
negatief, dus de sorteerfunctie herschikt de elementen willekeurig.


Antwoord 13

Ik vond deze variant hangen in de “verwijderd door auteur”-antwoorden op een duplicaat van deze vraag. In tegenstelling tot sommige van de andere antwoorden die al veel upvotes hebben, is dit:

  1. Eigenlijk willekeurig
  2. Niet aanwezig (vandaar de naam shuffledin plaats van shuffled)
  3. Hier nog niet aanwezig met meerdere varianten

Hier is een jsfiddle die het in gebruik laat zien.

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

Antwoord 14

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

Antwoord 15

Hier is de GEMAKKELIJKSTE,

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

voor een ander voorbeeld kunt u het hier

bekijken


Antwoord 16

Een recursieve oplossing:

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

Antwoord 17

Fisher-Yatesshuffle in javascript. Ik plaats dit hier omdat het gebruik van twee hulpprogramma’s (swap en randInt) het algoritme verduidelijkt in vergelijking met de andere antwoorden hier.

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

Antwoord 18

Moderne korte inline-oplossing met ES6-functies:

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

(voor educatieve doeleinden)


Antwoord 19

Kijk eerst hiervoor een geweldige visuele vergelijking van verschillende sorteermethoden in javascript.

Ten tweede, als je snel naar de bovenstaande link kijkt, zul je zien dat de random ordersortering relatief goed lijkt te presteren in vergelijking met de andere methoden, terwijl het extreem gemakkelijk en snel te implementeren is zoals hieronder weergegeven:

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

Bewerken: zoals aangegeven door @gregers, wordt de vergelijkingsfunctie aangeroepen met waarden in plaats van indices, daarom moet u indexOfgebruiken. Merk op dat deze wijziging de code minder geschikt maakt voor grotere arrays, aangezien indexOfin O(n)-tijd draait.


Antwoord 20

Alle andere antwoorden zijn gebaseerd op Math.random() wat snel is maar niet geschikt voor randomisatie op cryptgrafisch niveau.

De onderstaande code gebruikt het bekende Fisher-Yates-algoritme terwijl de Web Cryptography APIwordt gebruikt voor cryptografisch niveau van randomisatie.

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

Antwoord 21

een shuffle-functie die de bronarray niet verandert

Update: hier stel ik een relatief eenvoudig(niet vanuit complexiteitperspectief) en kortalgoritme voor dat zal prima werken met kleine arrays, maar het zal zeker veel meer kosten dan het klassieke Durstenfeld-algoritme als je te maken hebt met enorme arrays. Je kunt de Durstenfeldvinden in een van de beste antwoorden op deze vraag.

Oorspronkelijk antwoord:

Als u niet wiltdat uw shuffle-functie de bronarraymuteert, kunt u deze naar een lokale variabele kopiëren en de rest doen met een eenvoudige shuffle-logica.

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

Shuffling-logica: pak een willekeurige index, voeg het bijbehorende element toe aan de result arrayen verwijder het uit de source array-kopie. Herhaal deze actie totdat de bronarray leegwordt.

En als je het echt kort wilt, hier is hoe ver ik zou kunnen komen:

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

Antwoord 22

benchmarks

Laten we eerst de resultaten bekijken, dan bekijken we elke implementatie van shuffledhieronder –

  • splice

  • pop

  • inplace


Splice is traag

Elke oplossing die spliceof shiftin een lus gebruikt, zal erg traag zijn. Wat vooral opvalt als we de array vergroten. In een naïef algoritme hebben we –

  1. krijg een randpositie, i, in de invoerarray, t
  2. voeg t[i]toe aan de uitvoer
  3. splicepositie ivan array t

Om het langzame effect te overdrijven, demonstreren we dit op een reeks van een miljoen elementen. Het volgende script bijna 30 seconden

const shuffle = t =>
  Array.from(sample(t, t.length))
function* sample(t, n)
{ let r = Array.from(t)
  while (n > 0 && r.length)
  { const i = rand(r.length) // 1
    yield r[i]               // 2
    r.splice(i, 1)           // 3
    n = n - 1
  }
}
const rand = n =>
  Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via splice")
const result = shuffle(bigarray)
console.timeEnd("shuffle via splice")
document.body.textContent = JSON.stringify(result, null, 2)
body::before {
  content: "1 million elements via splice";
  font-weight: bold;
  display: block;
}

Antwoord 23

Je kunt het gemakkelijk doen met:

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

Antwoord 24

Met behulp van Fisher-Yatesshuffle-algoritme en ES6:

// Original array
let array = ['a', 'b', 'c', 'd'];
// Create a copy of the original array to be randomized
let shuffle = [...array];
// Defining function returning random value from i to N
const getRandomValue = (i, N) => Math.floor(Math.random() * (N - i) + i);
// Shuffle a pair of two elements at random position j
shuffle.forEach( (elem, i, arr, j = getRandomValue(i, arr.length)) => [arr[i], arr[j]] = [arr[j], arr[i]] );
console.log(shuffle);
// ['d', 'a', 'b', 'c']

Antwoord 25

We zijn nog steeds arrays aan het shuffelen in 2019, dus hier komt mijn aanpak, die netjes en snelvoor mij:

const src = [...'abcdefg'];
const shuffle = arr => 
  [...arr].reduceRight((res,_,__,s) => 
    (res.push(s.splice(0|Math.random()*s.length,1)[0]), res),[]);
console.log(shuffle(src));
.as-console-wrapper {min-height: 100%}

Antwoord 26

nog een andere implementatie van Fisher-Yates, met gebruik van de strikte modus:

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

Antwoord 27

Een eenvoudige wijziging van CoolAJ86’s antwoorddie de oorspronkelijke array niet wijzigt:

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

Antwoord 28

Matrix willekeurig maken

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; 

Antwoord 29

de kortste arrayShuffle-functie

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

Antwoord 30

Hoewel er al een aantal implementaties is geadviseerd, denk ik dat we het korter en gemakkelijker kunnen maken met forEach-lus, zodat we ons geen zorgen hoeven te maken over het berekenen van de array-lengte en we kunnen ook veilig het gebruik van een tijdelijke variabele vermijden.

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)

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Other episodes