Eine effiziente Art und Weise eine Anordnung von Randomisierung - Shuffle-Code

Question

wurde ich diese Frage in einem Interview gefragt und ich habe verschiedene Lösungen, aber der Interviewer war nicht überzeugt. Ich bin daran interessiert, eine Lösung zu finden. Bitte werfen Sie Ihre Ansichten:

F: eine effiziente Datenstruktur Schreiben Sie den Shuffle in einem iPod zu implementieren. Es muss alle Songs spielt, jedes Mal in verschiedener zufälliger Reihenfolge, das gleiche Lied soll nicht wiederholt werden. (Überwiegend O (n))

Eine Lösung, dachte ich nach dem Interview aus: Ich kann ein ohne Rekursion schnelle Art tun randomisiert. Wo wir zufällig wählte 1 Dreh O (1) und führen Sie dann quicksort O (n). Jetzt werden Lieder in einer bestimmten Reihenfolge sortiert werden, und ich spiele sie bis zum Ende. Sobald das Ende erreicht ist, werde ich wählte wieder eine zufällige Pivot und wiederholen Sie diesen Vorgang immer wieder.

Viele Grüße, Sethu

Answer 1

Legen Sie alle Songs in einer Reihe ... Für jedes Element in dem Array-Swap mit einer zufälligen Position.

Answer 2

Sie möchten die Fisher-Yates Shuffle . Beachten Sie die Implementierungsfehler auf dieser Seite erwähnt, als derzeit akzeptierte Antwort Foul eines fällt.

Answer 3

Nun, die erste lineare Zeitlösung, dass in dem Sinn:

Sie können eine verknüpfte Liste aller Songs machen, die über O (n) (vorausgesetzt, dass Einfügungen sind konstante Zeitbetrieb) nehmen würde. Dann erzeugt eine Zufallszahl, Modulo die Größe der Liste einen zufälligen Index zu erhalten, und diesen Index entfernen und fügen Sie ihn an eine neue Liste (beide sind konstante Zeitoperationen).

Einsetzinstrument für jedes O (n) + eine Entfernung für jeden O (n) + eine zweite Insertion O (n). Dies würde insgesamt zu einer linearen Zeit Lösung führen.

Bearbeiten : Ich habe ganz vergessen über die Liste gehen. Anstatt also, könnte man das Ergebnis eine feste Länge Array machen. Pop den Kopf der verknüpften Liste, weisen Sie den Zufallsindex und füllen Sie das Array.

Answer 4

Nates (bearbeitet) und Brian-Algorithmen sind die Fisher-Yates Shuffle O (n), während schlurfend durch das Sortieren O (n log n), kann aber tatsächlich schneller in der Praxis (http://en.wikipedia.org/wiki / Fisher% E2% 80% 93Yates_shuffle # Comparison_with_other_shuffling_algorithms). Erstes Lied schlurfende falsch mag unbedeutend Folgen haben, aber wenn Sie einen Misch-Algorithmus für ein Online-Poker-Spiel zu schreiben, stellen Sie sicher wissen, was Sie tun (http://www.cigital.com/news/index.php?pg= art & artid = 20).

Answer 5

Ich bin ein Anfänger, lassen Sie mir eine Lösung sagen, dass Streiks in dem Sinne, wenn etwas falsch ist, bitte machen Sie uns wissen.

Nehmen wir an, Lieder gespeichert werden entweder einzeln oder doppelt verknüpften Liste. Jedes Mal, wenn die Musik-Player weniger geöffnet wird, um eine Zufallszahl wählen als (eine beliebige Zahl, die Sie wünschen) annehmen k, und umgekehrt alle k Knoten in der Liste, ist es in ähnlicher Weise zweimal oder bei max dreimal tun (wie Sie wollen), die O nehmen würde ( 2n) oder O (3n) Zeit zu mischen. schließlich hat einen Zeiger auf den letzten Knoten in der Liste. Und jedes Mal, wenn ein Song gehört wird (ein Knoten besucht wird) entfernen Sie den Knoten, und legen Sie es neben dem letzten Knoten, der in O getan werden kann (1) Zeit. Dies setzt sich fort, bis die Musik-Player geschlossen ist.

Danke, Eager die Richtigkeit der Antwort zu kennen.

Answer 6

Was Sie wollen, ist die Fisher-Yates Shuffle . Hier ist eine Implementierung in Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

Wie es funktioniert, ist es das gesamte Array als Hut behandelt und beginnt zieht zufällige Elemente und Auskleiden sie an der Vorderseite des Arrays auf. Alle Elemente nach i sind ‚im Eimer‘, alle Elemente vor i gemischt werden.