Wie kann man ein JavaScript-Array randomisieren (mischen)?

1265

Ich habe ein Array wie dieses:

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

Wie kann ich es randomisieren / mischen?

Klicken Sie auf Upvote
quelle
6
Werfen Sie einfach die hier , dass Sie zufällig visualisieren , wie eine Shuffle - Funktion mit diesem Visualizer tatsächlich Mike Bostock ist: bost.ocks.org/mike/shuffle/compare.html
aug
5
@Blazemonger jsPref ist tot. Kannst du hier einfach posten, welches das schnellste ist?
eozzy
Was ist mit einem Einzeiler? Das zurückgegebene Array wird gemischt. arr1.reduce ((a, v) => a.splice (Math.floor (Math.random () * a.length), 0, v) && a, [])
brunettdan
Die Reduktionslösung hat eine O (n ^ 2) -Komplexität. Versuchen Sie, es auf einem Array mit einer Million Elementen auszuführen.
Riv

Antworten:

1541

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 )

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];
shuffle(arr);
console.log(arr);

Weitere Informationen zum verwendeten Algorithmus .

CoolAJ86
quelle
13
Die obige Antwort überspringt Element 0, die Bedingung sollte i--nicht sein --i. Außerdem ist der Test if (i==0)...überflüssig, da i == 0die while- Schleife niemals betreten wird. Der Anruf an Math.floorkann mit schneller erfolgen ...| 0. Entweder Tempi oder Tempj können entfernt und der Wert je nach Bedarf direkt myArray [i] oder j zugewiesen werden.
RobG
23
@prometheus, alle RNGs sind pseudozufällig, sofern sie nicht mit teurer Hardware verbunden sind.
Phil H
38
@RobG Die obige Implementierung ist funktional korrekt. Im Fisher-Yates-Algorithmus soll die Schleife nicht für das erste Element im Array ausgeführt werden. Schauen Sie sich Wikipedia an, wo es andere Implementierungen gibt, die ebenfalls das erste Element überspringen. Lesen Sie auch diesen Artikel, in dem erläutert wird, warum es wichtig ist, dass die Schleife nicht für das erste Element ausgeführt wird.
Theon
34
@nikola "überhaupt nicht zufällig" ist eine etwas starke Qualifikation für mich. Ich würde argumentieren, dass es ausreichend zufällig ist, es sei denn, Sie sind ein Kryptograf. In diesem Fall verwenden Sie Math.Random () wahrscheinlich überhaupt nicht.
Toon81
20
Ugh, yoda ( 0 !== currentIndex).
ffxsam
745

Hier ist eine JavaScript-Implementierung des Durstenfeld-Shuffle , einer optimierten Version von 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;
    }
}

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.

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]];
    }
}
Laurens Holst
quelle
22
ps Der gleiche Algorithmus wie die Antwort von ChristopheD, jedoch mit Erklärung und sauberer Implementierung.
Laurens Holst
12
Die Leute schreiben dem Algorithmus die falsche Person zu. Es ist nicht Fisher-Yates Shuffle, sondern Durstenfeld Shuffle . Der wahre ursprüngliche Fisher-Yates-Algorithmus wird in n ^ 2 Zeit ausgeführt, nicht in n Zeit
Pacerier
7
Dies ist nicht erforderlich, return arrayda 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.
Joel Trauger
5
Die Implementierung in dieser Antwort bevorzugt das untere Ende des Arrays. Auf die harte Tour herausgefunden . 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.
Marjan Venema
13
@MarjanVenema Sie sind sich nicht sicher, ob Sie diesen Bereich noch sehen, aber diese Antwort ist korrekt, und die von Ihnen vorgeschlagene Änderung führt tatsächlich zu Verzerrungen. Unter blog.codinghorror.com/the-danger-of-naivete finden Sie eine schöne Beschreibung dieses Fehlers.
user94559
133

Warnung!
Die Verwendung dieses Algorithmus wird nicht empfohlen , da er ineffizient und stark voreingenommen ist . Zeige Kommentare. Es wird hier zum späteren Nachschlagen belassen, weil die Idee nicht so selten ist.

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});
Deadrunk
quelle
13
Ich mag diese Lösung, genug, um einen einfachen Zufall zu geben
Alex K
147
Downvoting, da dies nicht wirklich so zufällig ist. Ich weiß nicht, warum es so viele positive Stimmen gibt. Verwenden Sie diese Methode nicht. Es sieht hübsch aus, ist aber nicht ganz richtig. Hier sind die Ergebnisse nach 10.000 Iterationen, wie oft jede Zahl in Ihrem Array den Index [0] erreicht (ich kann auch die anderen Ergebnisse angeben): 1 = 29,19%, 2 = 29,53%, 3 = 20,06%, 4 = 11,91%, 5 = 5,99%, 6 = 3,32%
radtad
8
Es ist in Ordnung, wenn Sie ein relativ kleines Array randomisieren müssen und sich nicht mit kryptografischen Dingen befassen müssen. Ich stimme voll und ganz zu, dass Sie eine komplexere Lösung verwenden müssen, wenn Sie mehr Zufälligkeit benötigen.
Deadrunk
21
Es ist auch die am wenigsten effiziente aller verfügbaren Methoden .
Blazemonger
12
Das Problem ist, dass es nicht deterministisch ist, was zu falschen Ergebnissen führt (wenn 1> 2 und 2> 3, sollte 1> 3 angegeben werden, dies garantiert dies jedoch nicht. Dies verwirrt die Sortierung und gibt das kommentierte Ergebnis an von @radtad).
MatsLindh
73

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;
}
con
quelle
42
Wirklich kein Vorteil, IMOHO, außer möglicherweise auf die Implementierung eines anderen zu stampfen.
user2864740
2
Wenn es im Array-Prototyp verwendet wird, sollte es einen anderen Namen als nur " Mischen" haben .
Wolf
57
Man könnte (oder sollte) vermeiden, native Prototypen zu erweitern: javascriptweblog.wordpress.com/2011/12/05/…
Wédney Yuri
12
Du solltest das nicht tun; Jedes einzelne davon betroffene Array kann mit for in nicht mehr sicher iteriert werden. Erweitern Sie keine nativen Prototypen.
18
@TinyGiant Eigentlich: Verwenden Sie keine for...inSchleifen, um über Arrays zu iterieren.
Conor O'Brien
69

Sie können es einfach mit Karte und Sortierung tun:

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 fügen jedes Element im Array in ein Objekt ein und geben ihm einen zufälligen Sortierschlüssel
  2. Wir sortieren mit dem Zufallsschlüssel
  3. Wir entfernen die Zuordnung, um die Originalobjekte zu erhalten

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.

überleuchtet
quelle
1
@superluminary Ups, du hast recht. Beachten Sie, dass diese Antwort bereits denselben Ansatz verwendet hat.
Bergi
@Bergi - Ah ja, Sie haben Recht, obwohl ich meine Implementierung etwas hübscher finde.
Superluminary
3
Sehr schön. Dies ist die Schwartzsche Transformation in js.
Mark Grimes
@torazaburo - Es ist nicht so performant wie Fischer Yates, aber es ist hübscher und der Code ist kleiner. Code ist immer ein Kompromiss. Wenn ich ein großes Array hätte, würde ich Knuth verwenden. Wenn ich ein paar hundert Gegenstände hätte, würde ich das tun.
Superluminary
1
@BenCarp - Einverstanden, es ist nicht die schnellste Lösung und Sie möchten sie nicht für ein massives Array verwenden, aber es gibt mehr Überlegungen im Code als die Rohgeschwindigkeit.
Superluminary
64

Verwenden Sie die Bibliothek underscore.js. Die Methode _.shuffle()ist für diesen Fall gut. 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();
vn_grv
quelle
12
Gute Antwort! Vielen Dank. Ich ziehe es den anderen Antworten vor, da es die Leute dazu ermutigt, Bibliotheken zu verwenden, anstatt überall potenziell fehlerhafte Funktionen zu kopieren und einzufügen.
Frabcus
60
@frabcus: Es macht keinen Sinn, eine ganze Bibliothek einzuschließen, nur um eine shuffleFunktion zu erhalten.
Blender
11
Ich bin mit @Blender nicht einverstanden. Es gibt viele Gründe, eine ganze Bibliothek einzuschließen, um eine Funktion zu erhalten, die Sie benötigen. Eine davon ist, dass das Risiko eines Fehlers geringer ist, wenn Sie ihn selbst schreiben. Wenn es sich um ein Leistungsproblem handelt, sollten Sie es nicht verwenden. Aber nur , weil es könnte ein Leistungsproblem bedeutet , es nicht sein wird.
Daniel Kaplan
7
@tieTYT: Warum brauchst du den Rest der Bibliothek? Das Fisher-Yates-Shuffle ist trivial zu implementieren. Sie benötigen keine Bibliothek, um ein zufälliges Element aus einem Array auszuwählen (ich hoffe). Es gibt also keinen Grund, eine Bibliothek zu verwenden, es sei denn, Sie verwenden tatsächlich mehr als eine Funktion daraus.
Blender
18
@Blender: Ich habe einen Grund dafür angegeben. 1) Ich versichere Ihnen, Sie können einen Fehler in jeden Code einfügen, den Sie schreiben, egal wie trivial er ist. Warum es riskieren? 2) Nicht voroptimieren. 3) In 99% der Fälle, in denen Sie ein Shuffle-Algo benötigen, geht es in Ihrer App nicht darum, ein Shuffle-Algo zu schreiben. Es geht um etwas, das einen Shuffle Algo braucht . Nutzen Sie die Arbeit anderer. Denken Sie nicht an Implementierungsdetails, es sei denn, Sie müssen.
Daniel Kaplan
50

NEU!

Kürzerer und wahrscheinlich * schnellerer Fisher-Yates-Shuffle-Algorithmus

  1. es verwendet während ---
  2. bitweise zum Boden (Zahlen bis zu 10 Dezimalstellen (32 Bit))
  3. Unnötige Verschlüsse und andere Dinge entfernt

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 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!).

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
}

Das Zwischenspeichern an einem anderen Ort var rnd=Math.randomund die anschließende Verwendung rnd()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.)

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
 }
}
cocco
quelle
6
überprüfen Sie die Leistung aus ... 2x schneller auf den meisten Browsern ... aber braucht mehr jsperf Tester ...
Cocco
10
js ist eine Sprache, die viele Verknüpfungen und verschiedene Arten des Schreibens akzeptiert. Obwohl es hier viele langsam lesbare Funktionen gibt, möchte ich nur zeigen, wie es auf eine performantere Weise gemacht werden kann, wobei auch einige Bytes gespeichert werden ... bitweise und Kurzschrift wird hier wirklich unterschätzt und das Web ist voll von fehlerhaftem und langsamem Code.
Cocco
Keine Slam Dunk Perf Steigerung. Wenn ich das fyund tausche shuffle prototype, bin ich fyin 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/3
Spig
Überprüfen Sie die Statistiken noch einmal ... Ich habe bereits geschrieben, dass Chrom langsamer ist, weil sie Mathe optimiert haben, auf allen anderen dem bitweisen Boden und während es schneller ist. Überprüfen Sie IE, Firefox, aber auch mobile Geräte. Wäre auch schön, Oper zu sehen ...
Cocco
1
Das ist eine schreckliche Antwort. SO ist kein Verdunkelungswettbewerb.
Welpe
39

Bearbeiten: 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:

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

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>

Kris Selbekk
quelle
Schön, aber erzeugt jedes Mal ein komplettes zufälliges Element?
DDD
Ich bin mir nicht ganz sicher, ob ich dich richtig verstanden habe. Dieser Ansatz mischt das Array in der Tat jedes Mal, wenn Sie das Sortierarray aufrufen, auf zufällige Weise (wenn auch pseudozufällig) - es ist aus offensichtlichen Gründen keine stabile Sortierung.
Kris Selbekk
4
Aus den gleichen Gründen wie unter stackoverflow.com/a/18650169/28234 erläutert . Dies führt viel eher dazu, dass frühe Elemente am Anfang des Arrays verbleiben.
AlexC
7
Dies ist ein großartiger, einfacher Einzeiler, wenn Sie ein Array verschlüsseln müssen, sich aber nicht zu sehr darum kümmern, dass die Ergebnisse akademisch nachweislich zufällig sind. Manchmal brauchen die letzten paar Zentimeter bis zur Perfektion mehr Zeit als es wert ist.
Daniel Griscom
1
Es wäre schön, wenn das funktionieren würde, aber es funktioniert nicht. Aufgrund der Funktionsweise der Schnellsuche wird ein inkonsistenter Komparator wahrscheinlich Array-Elemente nahe an ihrer ursprünglichen Position belassen. Ihr Array wird nicht verschlüsselt.
Superluminary
39

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 testShuffleArrayFunanderen Lösungen in Google Chrome durchgeführt]

Shuffle Array vorhanden

    function getShuffledArr (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 Rein, iterativ

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

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.

    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 Lösungen

Andere Lösungen nur zum Spaß.

ES6 Rein, rekursiv

    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 using 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 using 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]
        )
    }
Ben Carp
quelle
Wo ist der ES6 (ES2015)? [array[i], array[rand]]=[array[rand], array[i]]? Vielleicht können Sie skizzieren, wie das funktioniert. Warum iterieren Sie nach unten?
Sheriffderek
@sheriffderek Ja, die ES6-Funktion, die ich verwende, ist die Zuweisung von zwei Variablen gleichzeitig, wodurch wir zwei Variablen in einer Codezeile austauschen können.
Ben Carp
Dank an @sheriffderek, der den aufsteigenden Algorithmus vorgeschlagen hat. Der aufsteigende Algorithmus konnte in der Induktion bewiesen werden.
Ben Carp
23

Hinzufügen zu @Laurens Holsts Antwort. Dies ist zu 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
};
KingKongFrog
quelle
3
Wir sollten die Leute ermutigen, _.shuffle zu verwenden, anstatt Code aus dem Stapelüberlauf einzufügen. und wir sollten die Leute davon abhalten, ihre Stapelüberlaufantworten zu komprimieren. Dafür ist jsmin da.
David Jones
45
@ DavidJones: Warum sollte ich eine ganze 4-KB-Bibliothek einbinden, um ein Array zu mischen?
Blender
1
Der Aufruf von @KingKongFrog-Namen führt auch nicht zu einer Zusammenstellung einer vernünftigen Community.
Wheaties
2
Ist es effizient, var b = in einer Schleife zu arbeiten, anstatt b außerhalb der Schleife zu deklarieren und sie b = in einer Schleife zuzuweisen?
Alex K
2
@ Brian wird keinen Unterschied machen; Das Heben erfolgt, wenn der Quellcode analysiert wird. Nein wahrscheinlich beteiligt.
user2864740
23

Bearbeiten: Diese Antwort ist falsch

Siehe https://stackoverflow.com/a/18650169/28234 . Es wird hier als Referenz gelassen, weil die Idee nicht selten ist.

//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.5 ist eine Zufallszahl, die positiv oder negativ sein kann, sodass die Sortierfunktion Elemente zufällig neu anordnet.

Hakiko
quelle
17

Mit ES2015 können Sie Folgendes verwenden:

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

Verwendungszweck:

[1, 2, 3, 4, 5, 6, 7].shuffle();
BrunoLM
quelle
4
Zum Abschneiden sollten Sie n >>> 0anstelle von verwenden ~~n. Array-Indizes können höher als 2³¹-1 sein.
Oriol
1
Eine solche Destrukturierung sorgt für eine so saubere Implementierung +1
lukejacksonn
14

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:

  1. Eigentlich zufällig
  2. Nicht an Ort und Stelle (daher shuffledeher der Name als shuffle)
  3. Nicht bereits hier mit mehreren Varianten vorhanden

Hier ist eine jsfiddle, die zeigt, wie sie verwendet wird .

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}
Daniel Martin
quelle
(Ich vermute, es wurde gelöscht, da es eine sehr ineffiziente Methode ist, das Array zufällig zu sortieren, insbesondere für größere Arrays ... während die akzeptierte Antwort und eine Reihe anderer Klone dieser Antwort direkt randomisiert werden).
WiredPrairie
1
Ja, aber angesichts der Tatsache, dass die bekannte falsche Antwort immer noch eine Reihe von Stimmen enthält, sollte zumindest eine ineffiziente, aber korrekte Lösung erwähnt werden.
Daniel Martin
[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
Daniel Martin
3
Sie müssen verwenden, .sort(function(a,b){ return a[0] - b[0]; })wenn die Sortierung Werte numerisch vergleichen soll. Der Standardkomparator .sort()ist lexikografisch, was bedeutet 10, dass er kleiner als ist, 2da er 1kleiner als ist 2.
4castle
@ 4castle Okay, ich habe den Code aktualisiert, werde ihn aber zurücksetzen: Die Unterscheidung zwischen lexikografischer Reihenfolge und numerischer Reihenfolge spielt für Zahlen in dem Bereich, der 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))
Daniel Martin
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;
};
Tophe
quelle
Dies ist offensichtlich nicht so optimal wie der Fisher-Yates-Algorithmus, aber würde es für technische Interviews funktionieren?
Davidatthepark
@Andrea Der Code wurde beschädigt, weil die Array-Länge innerhalb der for-Schleife geändert wurde. Mit der letzten Bearbeitung wird dies korrigiert.
Charlie Wallace
11
arr1.sort(() => Math.random() - 0.5);
Sam Doidge
quelle
1
Warum minus 0,5? Was bedeutet diese Zahl?
Sartheris Stormhammer
1
@SartherisStormhammer, da wir eine compareFunction für die Sortierung verwenden und wenn diese eine Zahl größer als 0 zurückgibt, werden die verglichenen Elemente nur in Richtung geordnet. -0,5 auf Math.random () gibt uns ~ 50% der Zeit eine negative Zahl, was uns die umgekehrte Reihenfolge gibt.
Sam Doidge
Einfache und einfachste Lösung. Danke
Deanwilliammills
9

Sie können es leicht machen mit:

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

Weitere Informationen finden Sie unter JavaScript Sorting Arrays

Tính Ngô Quang
quelle
Dieser Algorithmus hat sich seit langem als fehlerhaft erwiesen.
Bitte beweise es mir. Ich basierte auf w3schools
Tính Ngô Quang
4
Sie können den Thread unter css-tricks.com/snippets/javascript/shuffle-array oder unter news.ycombinator.com/item?id=2728914 lesen . W3schools war und ist eine schreckliche Informationsquelle.
Eine gute Diskussion darüber, warum dies kein guter Ansatz ist, finden Sie unter stackoverflow.com/questions/962802/…
Charlie Wallace
8

Eine rekursive Lösung:

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));
};
julianisch
quelle
8

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.

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);
  }
}
Daniel Patru
quelle
7

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 orderSortierung im Vergleich zu den anderen Methoden relativ gut zu funktionieren scheint, während sie extrem einfach und schnell zu implementieren ist, wie unten gezeigt:

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

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 er indexOfin O (n) -Zeit ausgeführt wird.

Milo Wielondek
quelle
Array.prototype.sortÜbergibt zwei Werte als aund b, nicht den Index. Dieser Code funktioniert also nicht.
Gregers
@Gregers Sie haben Recht, ich habe die Antwort bearbeitet. Vielen Dank.
Milo Wielondek
1
Das ist nicht sehr zufällig. Abhängig von der Implementierung der Sortierung erfordert ein Element mit dem niedrigsten Array-Index möglicherweise mehr Vergleiche, um zum höchsten Index zu gelangen, als das Element neben dem höchsten Index. Dies bedeutet, dass es weniger wahrscheinlich ist, dass das Element am niedrigsten Index den höchsten Index erreicht.
1 'ODER 1 -
7

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 .

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

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:

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;
}
Evgenia Manolova
quelle
Dies ist im Wesentlichen der ursprüngliche Fisher-Yates-Algorithmus, wobei Sie spliceeine 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.
@torazaburo, danke für dein Feedback. Ich habe meine Antwort aktualisiert, um zu verdeutlichen, dass ich eher eine gut aussehende als eine superskalierende Lösung anbiete
Evgenia Manolova
Wir könnten die spliceMethode auch verwenden , um eine Kopie wie folgt zu erstellen : source = array.slice();.
Taiga
6

Hier ist die EINFACHSTE ,

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

Zum Beispiel können Sie es hier überprüfen

Aljohn Yamaro
quelle
5

Noch eine weitere Implementierung von Fisher-Yates im strengen 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;
}
Raphael C.
quelle
Welchen Wert bietet die strikte Hinzufügung der Verwendung gegenüber der akzeptierten Antwort?
Shortstuffsushi
Um mehr über den strengen Modus und seine Auswirkungen auf die Leistung zu erfahren, lesen Sie ihn hier: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
Raphael C
Hmm, könnten Sie auf etwas Bestimmtes aus dem Dokument verweisen, auf das verwiesen wird? Nichts dort scheint auf "Verbesserung der Leistung" zu verweisen, abgesehen von einem vagen Kommentar oben darüber, dass es für die js-Engine möglicherweise schwierig sein könnte, die Leistung zu optimieren. In diesem Fall ist mir unklar, welche Verwendung strikt verbessern würde.
Shortstuffsushi
Der strenge Modus gibt es schon seit geraumer Zeit, und es gibt genügend Lesungen, damit jeder seine eigene Meinung abgeben kann, ob er ihn immer verwenden sollte oder nicht und warum. Jslint zum Beispiel macht deutlich genug, dass Sie immer den strengen Modus verwenden sollten. Douglas Crockford hat eine ganze Reihe von Artikeln und einige großartige Videos darüber geschrieben, warum es wichtig ist, den strengen Modus immer zu verwenden, nicht nur als bewährte Methode, sondern auch, wie er von Browser-js-Engines wie V8 unterschiedlich interpretiert wird. Ich rate Ihnen dringend, es zu googeln und Ihre eigene Meinung dazu abzugeben.
Raphael C
Hier ist ein alter Thread über Perfs im strengen Modus, ein bisschen alt, aber immer noch relevant: stackoverflow.com/questions/3145966/…
Raphael C
5

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-YatesAlgorithmus, während er Web Cryptography APIfür die kryptografische Ebene der Randomisierung verwendet wird .

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

Marcin Malinowski
quelle
4

Moderne kurze Inline-Lösung mit ES6-Funktionen:

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

(zu Bildungszwecken)

icl7126
quelle
4

Eine einfache Änderung der Antwort von CoolAJ86, bei der das ursprüngliche Array nicht geändert wird :

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

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.

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)
Hafizur Rahman
quelle
4

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 wie Math.floor()bei positiven reellen Zahlen. Nur eine Abkürzung ist es.

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

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.

var shuffle = (a, l = a.length, r = ~~(Math.random()*l)) => l ? ([a[r],a[l-1]] = [a[l-1],a[r]], shuffle(a, l-1))
                                                              : a;

var arr = Array.from({length:3000}, (_,i) => i);
console.time("shuffle");
shuffle(arr);
console.timeEnd("shuffle");

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.

Reduzieren
quelle
3

Array zufällig sortieren

 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; 
Vickisys
quelle
Es sollte kein -1for n geben, wie Sie es <nicht <=
getan haben
3

die kürzeste arrayShuffleFunktion

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;
}
Tusko Trush
quelle
Anscheinend machst du Sattolo's anstelle von Fisher-Yates (Knuth, unvoreingenommen).
Arthur2e5
3

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 wirdMath.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:

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

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

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<s;i++) p.push(i);
    for(i=s-1; i>=0; i--) {
        j = Math.floor(n / fact[i]);
        n -= j*fact[i];
        q.push(p[j]);
        for(;j<i;j++) p[j]=p[j+1];
    }
    return q;
}

Was Sie jetzt nur wollen, ist:

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

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.

Thomas Baruchel
quelle
Auf jeden Fall elegant!
Gershom