Ich habe ein Array wie dieses:
var arr1 = ["a", "b", "c", "d"];
Wie kann ich es randomisieren / mischen?
javascript
arrays
random
shuffle
Klicken Sie auf Upvote
quelle
quelle
Antworten:
Der de facto unvoreingenommene Shuffle-Algorithmus ist der Fisher-Yates-Shuffle (auch bekannt als Knuth).
Siehe https://github.com/coolaj86/knuth-shuffle
Sie können hier eine großartige Visualisierung sehen (und den damit verknüpften Originalbeitrag )
Weitere Informationen zum verwendeten Algorithmus .
quelle
i--
nicht sein--i
. Außerdem ist der Testif (i==0)...
überflüssig, dai == 0
die while- Schleife niemals betreten wird. Der Anruf anMath.floor
kann mit schneller erfolgen...| 0
. Entweder Tempi oder Tempj können entfernt und der Wert je nach Bedarf direkt myArray [i] oder j zugewiesen werden.0 !== currentIndex
).Hier ist eine JavaScript-Implementierung des Durstenfeld-Shuffle , einer optimierten Version von Fisher-Yates:
Es wählt ein zufälliges Element für jedes ursprüngliche Array-Element aus und schließt es von der nächsten Ziehung aus, wie es zufällig aus einem Kartenspiel ausgewählt wird.
Dieser clevere Ausschluss tauscht das ausgewählte Element gegen das aktuelle aus, wählt dann das nächste zufällige Element aus dem Rest aus, schleift für eine optimale Effizienz rückwärts, stellt sicher, dass die zufällige Auswahl vereinfacht wird (sie kann immer bei 0 beginnen), und überspringt dabei das endgültige Element.
Algorithmus Laufzeit ist
O(n)
. Beachten Sie, dass das Mischen direkt durchgeführt wird. Wenn Sie also das ursprüngliche Array nicht ändern möchten, erstellen Sie zuerst eine Kopie davon mit.slice(0)
.BEARBEITEN: Aktualisierung auf ES6 / ECMAScript 2015
Mit dem neuen ES6 können zwei Variablen gleichzeitig zugewiesen werden. Dies ist besonders praktisch, wenn wir die Werte zweier Variablen austauschen möchten, da dies in einer Codezeile möglich ist. Hier ist eine kürzere Form derselben Funktion, die diese Funktion verwendet.
quelle
return array
da JavaScript Arrays als Referenz übergibt, wenn es als Funktionsargumente verwendet wird. Ich gehe davon aus, dass dies Platz spart, aber es ist eine interessante kleine Funktion. Durch das Mischen auf dem Array wird das ursprüngliche Array gemischt.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt () `. Siehe Generieren von zufälligen ganzen Zahlen in JavaScript in einem bestimmten Bereich? für eine sehr umfassende Erklärung.quelle
Man könnte (oder sollte) es als Prototyp von Array verwenden:
Von ChristopheD:
quelle
for...in
Schleifen, um über Arrays zu iterieren.Sie können es einfach mit Karte und Sortierung tun:
Sie können polymorphe Arrays mischen, und die Sortierung ist so zufällig wie bei Math.random, was für die meisten Zwecke gut genug ist.
Da die Elemente nach konsistenten Schlüsseln sortiert sind, die nicht bei jeder Iteration neu generiert werden, und jeder Vergleich aus derselben Verteilung stammt, wird jede Nicht-Zufälligkeit in der Verteilung von Math.random aufgehoben.
Geschwindigkeit
Die zeitliche Komplexität ist O (N log N), genau wie beim schnellen Sortieren. Die Raumkomplexität ist O (N). Dies ist nicht so effizient wie ein Fischer Yates-Shuffle, aber meiner Meinung nach ist der Code deutlich kürzer und funktionaler. Wenn Sie ein großes Array haben, sollten Sie auf jeden Fall Fischer Yates verwenden. Wenn Sie ein kleines Array mit einigen hundert Elementen haben, können Sie dies tun.
quelle
Verwenden Sie die Bibliothek underscore.js. Die Methode
_.shuffle()
ist für diesen Fall gut. Hier ist ein Beispiel mit der Methode:quelle
shuffle
Funktion zu erhalten.NEU!
Kürzerer und wahrscheinlich * schnellerer Fisher-Yates-Shuffle-Algorithmus
Skriptgröße (mit fy als Funktionsname): 90 Byte
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
LEISTUNG: http://jsperf.com/fyshuffle
Verwenden der am besten bewerteten Funktionen.
BEARBEITEN Es gab eine Berechnung im Übermaß (brauche nicht --c + 1) und niemand bemerkte es
kürzer (4 Bytes) und schneller (testen!).
Das Zwischenspeichern an einem anderen Ort
var rnd=Math.random
und die anschließende Verwendungrnd()
würden die Leistung auf großen Arrays ebenfalls geringfügig erhöhen.http://jsfiddle.net/vvpoma8w/2/
Lesbare Version (verwenden Sie die Originalversion. Dies ist langsamer, vars sind nutzlos, wie die Verschlüsse & ";", der Code selbst ist auch kürzer ... vielleicht lesen Sie dies Wie man Javascript-Code 'minimiert' , übrigens können Sie nicht Komprimieren Sie den folgenden Code in einem Javascript-Minifier wie dem obigen.)
quelle
fy
und tauscheshuffle prototype
, bin ichfy
in Chrome 37 unter OS X 10.9.5 (81% langsamer ~ 20.000 Operationen im Vergleich zu ~ 100.000) und Safari 7.1 bis zu ~ 8% langsamer. YMMV, aber es ist nicht immer schneller. jsperf.com/fyshuffle/3Bearbeiten: Diese Antwort ist falsch
Siehe Kommentare und https://stackoverflow.com/a/18650169/28234 . Es wird hier als Referenz gelassen, weil die Idee nicht selten ist.
Ein sehr einfacher Weg für kleine Arrays ist einfach folgender:
Es ist wahrscheinlich nicht sehr effizient, aber für kleine Arrays funktioniert dies einwandfrei. 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.
quelle
Zuverlässig, effizient, kurz
Einige Lösungen auf dieser Seite sind nicht zuverlässig (sie ordnen das Array nur teilweise zufällig an). Andere Lösungen sind deutlich weniger effizient. Mit
testShuffleArrayFun
(siehe unten) können wir Array-Shuffling-Funktionen auf Zuverlässigkeit und Leistung testen. Die folgenden Lösungen sind: zuverlässig, effizient und kurz (unter Verwendung der ES6-Syntax)[Vergleichstests wurden mit
testShuffleArrayFun
anderen Lösungen in Google Chrome durchgeführt]Shuffle Array vorhanden
ES6 Rein, iterativ
Zuverlässigkeits- und Leistungstest
Wie Sie auf dieser Seite sehen können, wurden hier in der Vergangenheit falsche Lösungen angeboten. Ich habe die folgende Funktion geschrieben und verwendet, um alle reinen (keine Nebenwirkungen) Array-Randomisierungsfunktionen zu testen.
Andere Lösungen
Andere Lösungen nur zum Spaß.
ES6 Rein, rekursiv
ES6 Pure using array.map
ES6 Pure using array.reduce
quelle
[array[i], array[rand]]=[array[rand], array[i]]
? Vielleicht können Sie skizzieren, wie das funktioniert. Warum iterieren Sie nach unten?Hinzufügen zu @Laurens Holsts Antwort. Dies ist zu 50% komprimiert.
quelle
var b =
in einer Schleife zu arbeiten, anstatt b außerhalb der Schleife zu deklarieren und sieb =
in einer Schleife zuzuweisen?Bearbeiten: Diese Antwort ist falsch
Siehe https://stackoverflow.com/a/18650169/28234 . Es wird hier als Referenz gelassen, weil die Idee nicht selten ist.
https://javascript.info/task/shuffle
quelle
Mit ES2015 können Sie Folgendes verwenden:
Verwendungszweck:
quelle
n >>> 0
anstelle von verwenden~~n
. Array-Indizes können höher als 2³¹-1 sein.Ich fand diese Variante in den Antworten "vom Autor gelöscht" auf einem Duplikat dieser Frage. Im Gegensatz zu einigen anderen Antworten, die bereits viele positive Stimmen haben, lautet dies:
shuffled
eher der Name alsshuffle
)Hier ist eine jsfiddle, die zeigt, wie sie verwendet wird .
quelle
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- Es gibt keine zufällige Sortierung, und wenn Sie es verwenden, können Sie sich schämen.sort(function(a,b){ return a[0] - b[0]; })
wenn die Sortierung Werte numerisch vergleichen soll. Der Standardkomparator.sort()
ist lexikografisch, was bedeutet10
, dass er kleiner als ist,2
da er1
kleiner als ist2
.Math.random()
erzeugt wird, keine Rolle . (Das heißt, die lexikografische Reihenfolge entspricht der numerischen Reihenfolge beim Umgang mit Zahlen von 0 (einschließlich) bis 1 (exklusiv))quelle
quelle
Sie können es leicht machen mit:
Weitere Informationen finden Sie unter JavaScript Sorting Arrays
quelle
Eine rekursive Lösung:
quelle
Fisher-Yates mischen in Javascript. Ich poste dies hier, weil die Verwendung von zwei Dienstprogrammfunktionen (swap und randInt) den Algorithmus im Vergleich zu den anderen Antworten hier verdeutlicht.
quelle
Schauen Sie sich hier zunächst einen großartigen visuellen Vergleich verschiedener Sortiermethoden in Javascript an.
Zweitens, wenn Sie sich den obigen Link genauer ansehen, werden Sie feststellen, dass die
random order
Sortierung im Vergleich zu den anderen Methoden relativ gut zu funktionieren scheint, während sie extrem einfach und schnell zu implementieren ist, wie unten gezeigt:Bearbeiten : Wie von @gregers hervorgehoben, wird die Vergleichsfunktion eher mit Werten als mit Indizes aufgerufen, weshalb Sie sie verwenden müssen
indexOf
. Beachten Sie, dass diese Änderung den Code für größere Arrays weniger geeignet macht, da erindexOf
in O (n) -Zeit ausgeführt wird.quelle
Array.prototype.sort
Übergibt zwei Werte alsa
undb
, nicht den Index. Dieser Code funktioniert also nicht.Eine Zufallsfunktion, die das Quellarray nicht ändert
Update : Hier schlage ich einen relativ einfachen (nicht aus Komplexitätssicht ) und kurzen Algorithmus vor, der mit kleinen Arrays gut funktioniert, aber definitiv viel mehr kostet als der klassische Durstenfeld- Algorithmus, wenn Sie mit großen Arrays arbeiten. Sie finden das Durstenfeld in einer der Top-Antworten auf diese Frage.
Ursprüngliche Antwort:
Wenn Sie nicht möchten, dass Ihre Shuffle-Funktion das Quell-Array mutiert , können Sie es in eine lokale Variable kopieren und den Rest mit einer einfachen Shuffling-Logik erledigen .
Mischlogik : Nehmen Sie einen zufälligen Index auf, fügen Sie das entsprechende Element zum Ergebnisarray hinzu und löschen Sie es aus der Kopie des Quellarrays . Wiederholen Sie diese Aktion, bis das Quellarray leer wird .
Und wenn Sie es wirklich kurz haben wollen, hier ist, wie weit ich kommen könnte:
quelle
splice
eine schrecklich ineffiziente Methode sind, um das zu tun, was sie als "Streik" bezeichneten. Wenn Sie das ursprüngliche Array nicht mutieren möchten, kopieren Sie es einfach und mischen Sie diese Kopie mit der viel effizienteren Durstenfeld-Variante.splice
Methode auch verwenden , um eine Kopie wie folgt zu erstellen :source = array.slice();
.Hier ist die EINFACHSTE ,
Zum Beispiel können Sie es hier überprüfen
quelle
Noch eine weitere Implementierung von Fisher-Yates im strengen Modus:
quelle
Alle anderen Antworten basieren auf Math.random (), das schnell ist, aber nicht für die Randomisierung auf kryptografischer Ebene geeignet ist.
Der folgende Code verwendet den bekannten
Fisher-Yates
Algorithmus, während erWeb Cryptography API
für die kryptografische Ebene der Randomisierung verwendet wird .quelle
Moderne kurze Inline-Lösung mit ES6-Funktionen:
(zu Bildungszwecken)
quelle
Eine einfache Änderung der Antwort von CoolAJ86, bei der das ursprüngliche Array nicht geändert wird :
quelle
Es gibt zwar bereits eine Reihe von Implementierungen, aber ich bin der Meinung, dass wir die Verwendung der forEach-Schleife kürzer und einfacher gestalten können, sodass wir uns nicht um die Berechnung der Array-Länge kümmern müssen und die Verwendung einer temporären Variablen sicher vermeiden können.
quelle
Nur um einen Finger in der Torte zu haben. Hier präsentiere ich eine rekursive Implementierung von Fisher Yates Shuffle (glaube ich). Es gibt eine einheitliche Zufälligkeit.
Hinweis: Der
~~
(Doppel-Tilde-Operator) verhält sich tatsächlich wieMath.floor()
bei positiven reellen Zahlen. Nur eine Abkürzung ist es.Bearbeiten: Der obige Code ist O (n ^ 2) aufgrund der Verwendung von,
.splice()
aber wir können Spleißen und Mischen in O (n) durch den Swap-Trick eliminieren.Das Problem ist, dass JS nicht mit großen Rekursionen weitermachen kann. In diesem speziellen Fall ist Ihre Array-Größe abhängig von Ihrer Browser-Engine und einigen unbekannten Fakten auf etwa 3000 bis 7000 begrenzt.
quelle
Array zufällig sortieren
quelle
-1
for n geben, wie Sie es<
nicht<=
die kürzeste
arrayShuffle
Funktionquelle
Aus theoretischer Sicht besteht meiner bescheidenen Meinung nach die eleganteste Methode darin, eine einzelne Zufallszahl zwischen 0 und n! -1 zu erhalten und eine Eins-zu-Eins-Zuordnung von
{0, 1, …, n!-1}
zu allen Permutationen von zu berechnen(0, 1, 2, …, n-1)
. Solange Sie einen (Pseudo-) Zufallsgenerator verwenden können, der zuverlässig genug ist, um eine solche Zahl ohne signifikante Verzerrung zu erhalten, verfügen Sie über genügend Informationen, um das zu erreichen, was Sie möchten, ohne mehrere andere Zufallszahlen zu benötigen.Wenn Sie mit IEEE754-Gleitkommazahlen mit doppelter Genauigkeit rechnen, können Sie davon ausgehen, dass Ihr Zufallsgenerator etwa 15 Dezimalstellen liefert. Da Sie 15! = 1.307.674.368.000 (mit 13 Ziffern) haben, können Sie die folgenden Funktionen für Arrays mit bis zu 15 Elementen verwenden und davon ausgehen, dass bei Arrays mit bis zu 14 Elementen keine signifikante Verzerrung vorliegt. Wenn Sie an einem Problem mit fester Größe arbeiten, bei dem diese Zufallsoperation mehrmals berechnet werden muss, sollten Sie den folgenden Code ausprobieren, der möglicherweise schneller als andere Codes ist, da er verwendet wird
Math.random
nur einmal verwendet wird (es sind jedoch mehrere Kopiervorgänge erforderlich).Die folgende Funktion wird nicht verwendet, aber ich gebe sie trotzdem; es gibt den Index einer gegebenen Permutation
(0, 1, 2, …, n-1)
gemäß der in dieser Nachricht verwendeten Eins-zu-Eins-Zuordnung zurück (der natürlichste bei der Aufzählung von Permuationen); Es soll mit bis zu 16 Elementen arbeiten:Der Kehrwert der vorherigen Funktion (erforderlich für Ihre eigene Frage) ist unten; Es ist beabsichtigt, mit bis zu 16 Elementen zu arbeiten. es gibt die Permutation der Ordnung n von zurück
(0, 1, 2, …, s-1)
:Was Sie jetzt nur wollen, ist:
Es sollte für bis zu 16 Elemente mit einer kleinen theoretischen Verzerrung funktionieren (obwohl dies aus praktischer Sicht nicht wahrnehmbar ist). es kann als voll verwendbar für 15 Elemente angesehen werden; Bei Arrays mit weniger als 14 Elementen können Sie davon ausgehen, dass absolut keine Verzerrung vorliegt.
quelle