Shuffle: Warum ist eine for-Schleife Umschaltung arr [i] mit arr [r] (r: Zufall 0 - Länge - 1) nicht eine gleichmäßig zufällige Shuffle?

Question

Ich nehme gerade Sedgewicks Algorithmen-Kurs auf Coursera (unterrichtet in Java). Er sagt, um einen gleichmäßig zufälligen Shuffling-Algorithmus zu erstellen, muss ich jeden Index i in meinem Array durchgehen und dieses Element mit einem zufälligen Element AUS NUR DEN ELEMENTEN, die ich SCHON GEDACHT HABE, austauschen. Er sagt, wenn ich das Element mit einem zufälligen Element aus dem gesamten Array austauschen würde, wäre es nicht gleichmäßig zufällig. Warum nicht? Wenn für jede Iteration das Element [I] völlig zufällig mit einem anderen Element im Array ausgetauscht wird, einschließlich sich selbst, dann ist 1/N immer die Wahrscheinlichkeit, wo das Element [I] enden wird; Ich sehe nicht, wie Voreingenommenheit eingeführt wird.

Mit anderen Worten: er spricht:

for (var i = 0; i < arr.length; i++){ 
    var r = Math.floor(Math.random() * i + 1) 
    swap(r, i); 
} 

über

for (var i = 0; i < arr.length; i++){ 
    var r = Math.floor(Math.random() * arr.length) 
    swap(r, i); 
} 

Excuse JavaScript als ich einen brandneuen Programmierer bin und bequemer mit ihm :)

Answer 1

Sehr einfach. Mathematik. Wenn Sie jedes Element mit einem anderen aus dem gesamten Satz wechseln, erhalten Sie am Ende eine Zufallszahl von 0 bis N-1, N-mal, und so gibt es N ** N mögliche Ergebnisse. Da sind N! (d. h. faktorielle N) mögliche Anordnungen der Gegenstände, und N ** N ist nicht durch N teilbar, einige Anordnungen werden häufiger als andere vorkommen.

Ein richtiger Shuffle wird beim ersten Durchlauf eine Zufallszahl von 0 bis N-1 wählen, dann den nächsten Durchgang von 0 bis N-2 usw., schließlich 0 bis 1. So wird es genau N geben ! mögliche Ergebnisse, jede der möglichen Permutationen (vorausgesetzt, Sie haben die Swaps richtig gemacht).