Zufallsausgabe

[Don P]

Hallo,

Sieht nach der perfekten Lösung aus ;-)
Nicht ganz, aber fast. So sind sie wirklich gleichverteilt:

function arrayShuffle(){

var tmp, rand;
  for(var i =0; i < this.length; i++){
    rand = i + Math.floor(Math.random() * (this.length - i));
    tmp = this[i];
    this[i] = this[rand];
    this[rand] = tmp;
  }
}
Array.prototype.shuffle =arrayShuffle;

  
Das schien mir erst nicht zu funktionieren. Dein Algorithmus  
  

> ~~~javascript
  

>   for(var i =0; i < this.length; i++){  
>     rand = i + Math.floor(Math.random() * (this.length - i));  
>   }

bevorzugt zweifellos große Werte für rand. Nach 10000 Durchläufen für ein Array mit 10 Elementen (= 100 000 Zufallswerte) ergibt sich z.B.:

rand:    0    1    2    3    4    5    6     7     8     9
Anzahl: 952 2103 3456 4745 6532 8447 10874 14272 19249 29370

Wie man sieht, steigt die Wahrscheinlichkeit für einen bestimmten rand-Wert mit dessen Größe stark an. Von Gleichverteilung kann da absolut nicht die Rede sein.

Hier werden die Elemente der Reihe nach aus den noch nicht verwendeten ausgewählt.

Das stimmt wohl, aber die Elemente [rand], gegen die getauscht wird, sind meistens die weiter "hinten" im Array, d.h. an Position 9, 8 usw.
Es wird also z.B. erst [0] mit [9] vertauscht, dann [1] mit [9], dann [2] mit [9], dann [3] mit [9] usw., so dass im großen Ganzen nur die Elemente von vorne nach hinten durch geschoben werden. Das ist von einer echten Zufallsverteilung weit entfernt, sollte man meinen.

Interessanterweise funktioniert es aber doch recht gut: Für ein Array mit 4 Elementen gibt es 4! = 24 Permutationen, so dass die Wahrscheinlichkeit für eine bestimmte Permutation 1/24 beträgt. Und siehe, ein Versuch mit 2 Millionen Durchläufen ergab im Schnitt 24,03228 Vertauschungen, bis eine bestimmte Permutation erreicht war. Das scheint mir kein schlechter Wert, verblüfft mich aber ziemlich. Vielleicht ist es aber doch ein schlechter Wert, denn es sind ja immerhin mehr als 3% Abweichung von der Theorie. Könnte mir vorstellen, dass das schon als signifikant gilt, kenne mich aber in der Statistik zu wenig aus.

Meine Funktion dagegen ergab für 2 Millionen Durchläufe im Schnitt 24,00359 Vertauschungen, bis eine bestimmte Permutation erreicht war. Hier war die Abweichung von der Theorie also 10 mal kleiner. Allerdings ist meine Lösung auch deutlich langsamer.

Gruß, Don P