Frage Wie wird ein JavaScript-Array zufällig gemischt (shuffle)?


Ich habe ein Array wie folgt:

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

Wie kann ich es zufällig mischen / mischen?


872
2018-03-15 22:37


Ursprung


Antworten:


Der de facto unverzerrte Shuffle-Algorithmus ist der Fisher-Yates (alias Knuth) Shuffle.

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

Sie können a sehen große Visualisierung hier (und der ursprüngliche Beitrag damit verbunden)

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

Einige weitere Informationen über den Algorithmus benutzt.


1084
2017-09-28 20:20



Hier ist eine JavaScript - Implementierung der Durstenfeld schlurft, eine computeroptimierte Version von 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;
    }
}

Der Fisher-Yates-Algorithmus arbeitet, indem er ein zufälliges Element für jedes ursprüngliche Array-Element auswählt und es dann von der nächsten Zeichnung ausschließt. So wie zufällig aus einem Kartenspiel.

Dieser Ausschluss erfolgt auf clevere Weise (erfunden von Durstenfeld für Computer), indem das ausgewählte Element mit dem aktuellen Element getauscht wird und dann das nächste zufällige Element aus dem Rest ausgewählt wird. Für eine optimale Effizienz läuft die Schleife rückwärts, so dass die zufällige Auswahl vereinfacht wird (sie kann immer bei 0 beginnen), und sie überspringt das letzte Element, da keine anderen Optionen mehr vorhanden sind.

Die Laufzeit dieses Algorithmus ist O (n). Beachten Sie, dass das Mischen an Ort und Stelle erfolgt. Wenn Sie also das ursprüngliche Array nicht ändern möchten, erstellen Sie zunächst eine Kopie davon .slice(0).

Aktualisierung auf ES6 / ECMAScript 2015

Mit dem neuen ES6 können wir zwei Variablen gleichzeitig zuweisen. Dies ist besonders nützlich, wenn wir die Werte von zwei Variablen austauschen möchten, da wir dies in einer Codezeile tun können. Hier ist eine kürzere Form der gleichen Funktion, die diese Funktion verwendet.

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

477
2017-09-06 04:55



[Community bearbeiten: Diese Antwort ist falsch; Zeige Kommentare. Es wird hier für zukünftige Referenz gelassen, weil die Idee nicht so selten ist.]

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

85
2018-04-13 13:59



Man könnte (oder sollte) es als Prototyp von Array verwenden:

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

69
2018-03-31 05:29



Verwenden Sie die Bibliothek "underscore.js". Die Methode _.shuffle() ist schön für diesen Fall. Hier ist ein Beispiel mit der 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();

56
2017-09-22 23:21



NEU!

Kürzere und wahrscheinlich * schnellere Fisher-Yates Shuffle-Algorithmen

  1. es benutzt während ---
  2. bitweise bis zum Boden (Zahlen bis zu 10 Dezimalziffern (32bit))
  3. entfernte unnötige Verschlüsse und andere Sachen

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
}

Skriptgröße (mit fy als Funktionsname): 90 Bytes

DEMO http://jsfiddle.net/vvpoma8w/

* schneller wahrscheinlich auf allen Browsern außer Chrome.

Wenn Sie Fragen haben, fragen Sie einfach.

BEARBEITEN

Ja, es ist schneller

PERFORMANCE:  http://jsperf.com/fyshuffle

Verwenden der oben gewählten Funktionen.

BEARBEITEN  Es gab eine Berechnung im Übermaß (brauche nicht --c + 1) und niemand hat es bemerkt

kürzer (4 Bytes) und schneller (testen Sie es!).

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
}

Caching woanders var rnd=Math.random und dann benutzen rnd() würde auch die Leistung bei großen Arrays leicht erhöhen.

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

Lesbare Version (Verwenden Sie die Originalversion. Das ist langsamer, Vars sind nutzlos, wie die Closures & ";", der Code selbst ist auch kürzer ... vielleicht lesen Sie das Wie man Javascript-Code "verkleinert" Außerdem können Sie den folgenden Code in einem Javascript-Minifier wie dem oben genannten nicht komprimieren.

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

45
2018-04-05 15:38



Ein sehr einfacher Weg für kleine Arrays ist einfach das:

const someArray = [1, 2, 3, 4, 5];

someArray.sort(() => Math.random() - 0.5);

Es ist wahrscheinlich nicht sehr effizient, aber für kleine Arrays funktioniert das gut. Hier ist ein Beispiel, damit Sie sehen können, wie zufällig (oder nicht) es ist und ob es zu Ihrem Anwendungsfall passt oder nicht.

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>


23
2017-10-03 13:16



Sie können es leicht mit Karte und sortieren:

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. Wir setzen jedes Element in das Array in einem Objekt und geben ihm einen zufälligen Sortierschlüssel
  2. Wir sortieren mit dem Zufallsschlüssel
  3. Wir heben die Zuordnung auf, um die Originalobjekte zu erhalten

Sie können polymorphe Arrays mischen, und die Sortierung ist so zufällig wie Math.random, was für die meisten Zwecke gut genug ist.

Da die Elemente nach konsistenten Schlüsseln sortiert sind, die nicht bei jeder Wiederholung neu generiert werden, und jeder Vergleich aus derselben Verteilung zieht, wird jede Nicht-Zufälligkeit in der Verteilung von Math.random aufgehoben.


23
2018-04-01 21:23



Hinzufügen zu @Laurens Holsts Antwort. Dies ist 50% komprimiert.

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

19
2017-12-20 04:15