nicht angemeldet
Zufallsausgabe
2 0 0 0 
Gunnar Bittersmann
0 0 1 
JürgenB
1 Gunnar Bittersmann
0 0 
Kai345
0 Gunnar Bittersmann
Zufallsausgabe
MudGuard
StruppiHallo zusammen,
brauch ein Script das mit wenn man sagen wir mal 14Mitglieder hat, 14 verschiedene Zahlen ausgibt als Zufallsausgabe. Die Ausgabe klappt, aber sind immer noch doppelte dadrin. Hab den Krempel mal in ein Array gestopft, aber wie kann ich das machen, dass ich das vergleiche oder der mit 14 Zahlen ausgibt ohen DOPPELTE.
<html>
<head>
<script type="text/javascript">
function machWas()
{
var gruppe=document.Formular.gruppe.value;
var mitglieder=document.Formular.mitglieder.value;
var anzahl=mitglieder/gruppe;
var zahlen = new Array();
document.write("<form name="Formular1">");
for(i=0; i<mitglieder; i++)
{
var bla=Math.round(Math.random()*mitglieder+1);
zahlen[i]=bla;
}
document.write("</form>");
alert(zahlen);
}
</script>
</head>
<body>
<form name="Formular">
Gruppe<input type="text" name="gruppe"><br>
Mitglieder<input type="text" name="mitglieder">
<input type="button" value="abschicken" onClick="machWas()">
</form>
</body>
</html>
Gruß
-
brauch ein Script das mit wenn man sagen wir mal 14Mitglieder hat, 14 verschiedene Zahlen ausgibt als Zufallsausgabe. Die Ausgabe klappt, aber sind immer noch doppelte dadrin.
Du meinst ArrayShuffle?
Siechfred
--
Hinter den Kulissen passiert viel mehr, als man denkt, aber meistens nicht das, was man denkt.-
Hallo Siechfred,
Du meinst ArrayShuffle?
Sieht nach der perfekten Lösung aus ;-)
Mit freundlichem Gruß
Micha-
SPITZE hab daraus ne schicke Lösung basteln können.
Gruß
-
Hello out there!
SPITZE hab daraus ne schicke Lösung basteln können.
Ganz gewiss nicht!! Siehe https://forum.selfhtml.org/?t=163655&m=1066385
Eine Lösung, ein Array wirklich zu durchmischen, sähe so aus:
var sortedArray = ["A", "B", "C", "D"]; var shuffledArray = new Array(); for (var i = sortedArray.length; i > 1;) { var r = Math.floor(Math.random() * i); // Zufallszahl aus Bereich 0 ≤ r < i // Bereich nimmt mit jedem Schleifendurchlauf um 1 ab shuffledArray[--i] = sortedArray[r]; // vermindere Schleifenindex // kopiere zufällig ausgewähltes Element ans Ende des Zielarrays sortedArray.splice(r, 1); // lösche eben kopiertes Element aus Ursprungsarray // damit ist vermindertes i gleich aktueller sortedArray.length } shuffledArray[0] = sortedArray[0];Eine andere Lösung wäre, einmal eine ganzzahlige Zufallszahl r aus dem Bereich 0 ≤ r < n! (n = sortedArray.length; n! = 1 * 2 * 3 * ... * n) zu ziehen und anhand dieser diejenige Permutation auszugeben, die in der sortierten Liste aller Permutationen an r-ter Stelle steht.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)-
Hi,
Eine andere Lösung wäre, einmal eine ganzzahlige Zufallszahl r aus dem Bereich 0 ≤ r < n! (n = sortedArray.length; n! = 1 * 2 * 3 * ... * n) zu ziehen und anhand dieser diejenige Permutation auszugeben, die in der sortierten Liste aller Permutationen an r-ter Stelle steht.
Au ja. Das ist wirklich ne praktikable Lösung.
David wollte was für 14 User. 14! = 87178291200, also für rund 87 Milliarden Permutationen.
Schreibst Du mal schnell die sortierte Liste aller rund 87 Milliarden Permutationen auf?
Selbst wenn für jede Permutation nur ein einzelnes Byte gebraucht würde (was definitiv nicht ausreicht!), wären das 87 Gigabyte. Damit dürften die meisten Browser ein Problem bekommen ...cu,
Andreas--
Warum nennt sich Andreas hier MudGuard?
O o ostern ...
Fachfragen unaufgefordert per E-Mail halte ich für unverschämt und werde entsprechende E-Mails nicht beantworten. Für Fachfragen ist das Forum da.
-
Hello out there!
Eine andere Lösung wäre, einmal eine ganzzahlige Zufallszahl r aus dem Bereich 0 ≤ r < n! (n = sortedArray.length; n! = 1 * 2 * 3 * ... * n) zu ziehen und anhand dieser diejenige Permutation auszugeben, die in der sortierten Liste aller Permutationen an r-ter Stelle steht.
Au ja. Das ist wirklich ne praktikable Lösung.
David wollte was für 14 User. 14! = 87178291200, also für rund 87 Milliarden Permutationen.
Schreibst Du mal schnell die sortierte Liste aller rund 87 Milliarden Permutationen auf?Grmpf, das kommt davon, wenn man mal nicht den Konjunktiv benutzt ...
Es war nicht die Rede davon, alle Permutationen aufzulisten, sondern diejenige Permutation auszugeben, die in der sortierten Liste aller Permutationen an r-ter Stelle STÜNDE.
Um die r-te Permutation der Liste auszugeben, muss man nicht die ganze Liste ermitteln; ein Algorithmus kann zu gegebenem r einfach nur die r-te Permutation ausgeben.
See ya up the road,
GunnarPS. Und falls sich doch jemand die Mühe macht, alle rund 87 Milliarden Permutationen aufzuschreiben, dann STEHT sie an der Stelle. ;-b
--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)
-
-
-
-
Hello out there!
Du meinst ArrayShuffle?
Sieht nach der perfekten Lösung aus ;-)
Nein, das sieht nach ziemlichem Mist aus. Alles andere als perfekt.
Bevor man in höchsten Tönen schwelgt, sollte man sich doch erst mal ein paar Gedanken machen.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers) -
Hallo Micha,
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;Hier werden die Elemente der Reihe nach aus den noch nicht verwendeten ausgewählt. Wenn man das geschickt macht, kommt man genau so mit einem Array aus (ich habe den Algorithmus ja fast nicht abgeändert).
Grüße
Daniel
-
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 29370Wie 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
-
Hello out there!
Das schien mir erst nicht zu funktionieren. Dein Algorithmus
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. Zweifellos. Muss ja auch: Beim 1. Schleifendurchlauf ist rand aus dem Intervall [0, this.length[; beim 2. Schleifendurchlauf ist rand aus dem Intervall [1, this.length[; beim 3. Schleifendurchlauf ist rand aus dem Intervall [2, this.length[ ... Beim 2. Schleifendurchlauf steht das Element rand[0] des am Ende auszugebenden Arrays schon fest und soll dann nicht mehr geändert werden; beim 2. Schleifendurchlauf steht das Element rand[1] des am Ende auszugebenden Arrays schon fest und soll dann nicht mehr geändert werden ... > rand: 0 1 2 3 4 5 6 7 8 9 > Anzahl: 952 2103 3456 4745 6532 8447 10874 14272 19249 29370 Zu erwartet gewesen wären\* (gerundet): 1000 2111 3361 4790 6456 8456 10956 14290 19290 29290 > 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. Nicht rand soll gleichverteilt sein, sondern die Permutationen der Arrayelemente. > > Das ist von einer echten Zufallsverteilung weit entfernt, sollte man meinen. Nö, passt schon. Testen kannst du solch einen Algorithmus, in dem du jedes Vorkommen von `Math.floor(Math.random() * n)`{:.language-javascript} durch eine Schleife `for (var i = 0; i < n; i++)`{:.language-javascript} ersetzt; dann hast du nämlich die Zahlen von 0 bis n - 1 wirklich gleichverteilt erzeugt. See ya up the road, Gunnar \* Berechnung: 1/10 \* 10000 = 1000 (1/10 + 1/9) \* 10000 = 2111.11111 (1/10 + 1/9 + 1/8) \* 10000 = 3361.11111 (1/10 + 1/9 + 1/8 + 1/7) \* 10000 = 4789.68254 -- „Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ ([Kirsten Evers](https://forum.selfhtml.org/?t=158750&m=1033264)) -
Hallo Don,
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.Doch, Du betrachtest nur die falschen Werte. Ich halte im forderen Teil des Arrays die schon ausgewählten Elemente, und im hinteren Teil die, aus denen noch ausgewählt werden kann.
Aus denen noch wählbaren Elementen wird jedes mal mit gleicher Wahrscheinlichkeit gezogen. Dadurch, dass das immer weniger werden und sie sich im hinteren Teil befinden, werden die rand-Werte natürlich immer größer, das spielt aber keine Rolle.
Mein Algorithmus macht im Prinzip etwas sehr ähnliches, wie Deiner. Du wählst immer zufällig eine noch leere Stelle aus, während ich immer zufällig ein noch nicht verwendetes Element auswähle.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.
Den unterschied würde ich auf unterschiedliche Auswirkung nummerischer Fehler zurückführen. Mit perfekten, reellen Zufallszahlen sind beide wählen beide Algorithmen Permutationen perfekt gleicherteilt. Nun sind Floating-Point-Zahlen aber natürlich diskretisiert. Dadurch wird es gewisse Fehler geben.
Wenn Du die Güte der Algorithmen vergleichen willst, solltest Du aber sowieso nicht die Anzahl der Vertauschungen zählen, sondern die Häufigkeit von Permutationen zählen.
Nimm vielleicht ein paar mehr Elemente (so 6 bis 8 gehen noch) und zähle die Häufigkeit, mit der die verschiedenen Permutationen vorkommen.Ich hab das mal kurz mit Java ausprobiert:
private static Random random = new Random(); public static void main(String[] argv) { int limit = 10000000; Map<String, Integer> permutations = new HashMap<String, Integer>(); for (int i = 0; i < limit; ++i) { int[] array = new int[] {0, 1, 2, 3, 4, 5, 6}; shuffle(array); String s = Arrays.toString(array); Integer count = permutations.get(s); if (count == null) { count = 0; } ++count; permutations.put(s, count); if (i % 100000 == 0) { System.out.println(i); } } double d = (double) limit / (double) factorial(7); double error = 0; String perm = ""; double errorSum = 0; for (Map.Entry<String, Integer> entry: permutations.entrySet()) { double e = Math.abs(d - (double) entry.getValue()); if (e > error) { error = e; perm = entry.getKey(); } } System.out.println(); System.out.println("max abs error: " + error); System.out.println("avg abs error: " + errorSum / (double) limit); System.out.println("max rel error: " + error / d); System.out.println("avg rel error: " + errorSum / d / (double) limit); } public static void shuffle(int[] array) { for (int i = 0; i < array.length; ++i) { int r = i + (int) Math.floor(random.nextDouble() * (array.length - i)); int t = array[i]; array[i] = array[r]; array[r] = t; } } public static int factorial(int i) { int r = 1; for (int j = 2; j <= i; ++j) { r *= j; } return r; }Ergebnisse bei mir: (mit 7 Elementen und 10 Mio. aufrufen)
max abs error: 166.8730158730159
avg abs error: 0.0
max rel error: 0.08410400000000001
avg rel error: 0.0Das sieht doch ziemlich gut aus. Um auch die maximale Abweichung noch kleiner zu bekommen, bräuchte man wohl noch mehr durchläufe.
Grüße
Daniel
-
-
Hallo Daniel,
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;und wenn du die for- durch eine abwärtslaufende do-while-Schleife ersetzt, wird es sogar noch etwas schneller: ~~~javascript Array.prototype.shuffle=function() { var l=this.length,t,zi,i=l; do { zi=Math.floor(Math.random()*i); t=this[zi]; this[zi]=this[--i]; this[i]=t; } while (i); }Gruß, Jürgen
-
-
Hallo Mathias,
Ihr seid toll. Wollt ich nur mal sagen.
danke.
Vieleicht solltet ihr bei der nächsten selfhtml-Version einige Beispiele zum Problem Zufall angeben. Sonst "geistern" Algorithmen wie der von Siechfred in gutem Glauben verlinkte, aber auch Konstrukte wie "Math.round(Math.random())" ewig weiter durch die Foren.
Gruß, Jürgen
-
-
hallo jungs,
und wenn du die for- durch eine abwärtslaufende do-while-Schleife ersetzt, wird es sogar noch etwas schneller:
Array.prototype.shuffle=function() {
var l=this.length,t,zi,i=l;
do {
zi=Math.floor(Math.random()*i);
t=this[zi];
this[zi]=this[--i];
this[i]=t;
} while (i);
}ich haette auch noch eine loesung anzubieten: ~~~javascript Array.prototype.shuffle = (function () { this.sort(function () { return (0.5 - Math.random()); }); }); ~~~ ... ... oder etwas umfangreicher als bausatz namens »Math.randomize«: <http://www.pseliger.de/jsExtendedApi/jsApi.Math.randomize.dev.js> bzw. <http://www.pseliger.de/jsExtendedApi/jsApi.Math.randomize.js>, ... ... wobei ich niemals ausprobiert habe, wie nah die loesungen aus dieser methode an eine hinreichend genaue gleichverteilung heranreichen. was haltet Ihr davon? so long - peterS. - pseliger@gmx.net -- »Because objects in JavaScript are so flexible, you will want to think differently about class hierarchies. Deep hierarchies are inappropriate. Shallow hierarchies are efficient and expressive.« - [Douglas Crockford](http://javascript.crockford.com/) [ie:( fl:) br:> va:( ls:& fo:) rl:) n3;} n4:} ss:} de:µ js:} mo:? zu:\]](http://www.peter.in-berlin.de/projekte/selfcode/?code=ie%3A%28+fl%3A%29+br%3A%3E+va%3A%28+ls%3A%26+fo%3A%29+rl%3A%29+n3%3B%7D+n4%3A%7D+ss%3A%7D+de%3A%B5+js%3A%7D+mo%3A%3F+zu%3A%5D)-
ich haette auch noch eine loesung anzubieten:
Array.prototype.shuffle = (function () {
this.sort(function () {
return (0.5 - Math.random());
});
});Die war hier auch schon im Gespräch, sie zwar absolut elegant aber auch extrem langsam. Struppi.-
Hallo Struppi,
Array.prototype.shuffle = (function () {
this.sort(function () {
return (0.5 - Math.random());
});
});
Die war hier auch schon im Gespräch, sie zwar absolut elegant aber auch extrem langsam.Sie ist nicht elegant sonder kriminell...
Sort setzt voraus, dass die übergebene Funktion eine Ordnung realisiert, das ist bei Random aber natürlich nicht der Fall. Damit hat man keinerlei Aussage mehr darüber, was das tut, noch nicht mal, dass es überhaupt terminiert.
Eine Gleichverteilung kommt auch höchstens dann zustande, wenn das dazu führt, dass der eingesetzte Algorithmus so lange auf dem Array rumeiert, dass da eine Gleichverteilung zustande kommt, unabhängig davon, was er genau tut.Grüße
Daniel
-
Hallo Daniel,
Sie ist nicht elegant sonder kriminell...
Sort setzt voraus, dass die übergebene Funktion eine Ordnung realisiert, das ist bei Random aber natürlich nicht der Fall. Damit hat man keinerlei Aussage mehr darüber, was das tut, noch nicht mal, dass es überhaupt terminiert.
Eine Gleichverteilung kommt auch höchstens dann zustande, wenn das dazu führt, dass der eingesetzte Algorithmus so lange auf dem Array rumeiert, dass da eine Gleichverteilung zustande kommt, unabhängig davon, was er genau tut.das kann ich nicht bestätigen. Ein schneller Test im IE und im FF zeigt, dass der Algorithmus funktioniert und allenfalls etwas langsamer ist.
Gruß, Jürgen
-
Hallo JürgenB,
das kann ich nicht bestätigen. Ein schneller Test im IE und im FF zeigt, dass der Algorithmus funktioniert und allenfalls etwas langsamer ist.
Klar, wenn man Glück hat, führt das dazu, dass jedes Element an eine zufällige Stelle getauscht wird. Die Betonung liegt eben auf "wenn man Glück hat".
Nun mag es im Web-Umfeld generell üblich sein, dass man sich darauf verlässt, dass man Glück hat, aber im Allgemeinen ist das keine empfehlenswerte Entwicklungsstrategie.
Mir ist klar, dass da normalerweise irgend ein durchmischen passiert. (Hast Du mal überprüft, wie gleichverteilt die erzeugten Permutationen wirklich sind?).
Der entscheidende Punkt ist, dass man die Spezifikation der sort-Funktion verletzt, indem man einen ungültigen Vergleich verletzt.
Für einen Vergleich müssen eben ein paar Eigenschaften gelten wie a < b --> !(b <= a), a < b & b < c --> a < c, a < b | b <= b. Die erfüllt Random nicht. Da man auch noch mit vielen Implementierungen zu tun hat, die sich auch beliebig ändern können, kann man sich überhaupt nicht darauf verlassen, dass man das mal ausprobiert hat.
Als "kriminell" hab ich das nicht bezeichnet, weil es nicht in gängigen Browsern funktionieren würde (das tut es ja, klar), sondern weil solche Spezifikationsverletzung eine äußerst unsaubere und gefährliche Art ist zu programmieren. Solche Hacks sollte man tunlichst vermeiden, wenn man an zuverlässiger Software interessiert ist, auch wenn es bei Web-Javascript-Basteleien da nicht so drauf ankommen mag.Grüße
Daniel
-
Hallo Daniel,
die Spezifikationen der Sort-Methode habe ich mir jetzt nicht angesehen, und ich möchte ja auch keine Reklame für den Mischalgorithmus von Peter machen.
Bei meinem Schnelltest habe ich die Algorithmen nur 5000 mal Arrays mit 4, 5 und 6 Elementen mischen lassen. Das sind eigentlich noch zu wenig Durchläufe, um eine ordentliche Statistik zu erhalten. Gemessen habe ich dann, wie oft jede Verteilung vorkommt und den kleinsten und größten Wert ausgegeben. Hierbei waren die Algorithmen von Gunnar, von Peter, von Dir und von mir gleich gut und nur unterschiedlich schnell.
Gruß, Jürgen
-
Hallo JürgenB,
die Spezifikationen der Sort-Methode habe ich mir jetzt nicht angesehen, und ich möchte ja auch keine Reklame für den Mischalgorithmus von Peter machen.
Ok ;-)
Mit meinem Java-Testprogramm komme ich auf diese Zahlen:
sort mit random:
max abs error: 174064.87301587302
avg abs error: 1.202104514285684
max rel error: 87.728696
avg rel error: 6.058606751999847E-4"mein" Algorithmus:
max abs error: 214.1269841269841
avg abs error: 0.018118590476190487
max rel error: 0.10791999999999999
avg rel error: 9.131769600000006E-6Die Sort-Variante ist da nicht wirklich schlecht im Mittel, wenn auch meine Variante nochmal deutlich besser ist. Allerdings gibt es offensichtlich einen (oder vermutlich eher ein paar) drastische Ausreißer.
Die Zahlen von gestern stimmen übrigens nicht ganz, weil errorSum in meinem Programm gar nicht aufaddiert wurde. Das hab ich jetzt korrigiert, sodass auch die Durchschnittswerte berechnet werden.
Grüße
Daniel
-
-
-
-
-
-
Hallo peterS.,
ich haette auch noch eine loesung anzubieten:
Array.prototype.shuffle = (function () {
this.sort(function () {
return (0.5 - Math.random());
});
});die Mischqualität ist wie bei meinem Algorithmus, aber, wie Struppi schon schrieb, sie braucht etwa dreimal so lange. Gruß, Jürgen
-
-
Hallo JürgenB,
While-Schleifen um einfach nur hoch oder runter zu zählen und "--" inline mag ich nicht besonders, aber mir ist gerade noch aufgefallen, dass das auch so geht:
public static void shuffle(int[] array) { for (int i = 0; i < array.length; ++i) { int r = random.nextInt(i + 1); int t = array[i]; array[i] = array[r]; array[r] = t; } }Ganz nett ist vielleicht zu überlegen, warum auch diese Variante stimmt.
Mit einer while-Shleife könnte man nuch das i + 1 und einen Aufruf von nextInt sparen (Der erste Aufruf liefert ja immer 0).
Aber ersteres schenke ich mir mal und letzteres überlasse ich dem Compiler ;-)Grüße
Daniel
-
Hallo Daniel,
habe diese Antwort übersehen, daher kommt meine Antwort so spät.
While-Schleifen um einfach nur hoch oder runter zu zählen und "--" inline mag ich nicht besonders, ...
ich habe irgendwo (Quelle leider nicht gemerkt) mal gelesen, das in den meisten Sprachen while-Schleifen schneller sind, als for-Schleifen. Lässt man den Zähler rückwärts laufen, muss man nur auf "=0" testen, was auch schneller geht, als "<n", da sich hinter Vergleichen fast immer eine Subtraktion mit anschließendem Test auf "=0" (Zero-Flag) oder "<0" (Vorzeichen-Flag, MSB, ...) verbirgt.
int r = random.nextInt(i + 1);da ich von Java keine Ahnung habe und daher nextInt nicht kenne, kann ich diese Version auch nicht beurteilen.
Gruß, Jürgen
-
-
-
-
-
Hello out there!
Du meinst ArrayShuffle?
2× „hilfreich“?? Ich plädiere für die Wiedereinführung der „Nicht-hilfreich“-Bewertung.
Der dort vorgestellte Algorithmus ist ziemlicher Mist. Von einem solchen Algorithmus sollte man doch erwarten, dass er alle möglichen Permutationen mit gleicher Wahrscheinlichkeit ausgibt. Das kann dieser Algorithmus (für Anzahl der Elemente n > 2) gar nicht leisten. (Den Beweis spare ich mir für ein separates Posting auf.)
Schauen wir mal, wie schlecht er wirklich ist:
n = 3:
Wenn dreimal 0 als Zufallszahl gezogen wird:
tausche A[0] mit A[0] ABC → ABC
tausche A[1] mit A[0] ABC → BAC
tausche A[2] mit A[0] BAC → CABDas durchgerechnet ergibt:
000 CAB
001 BCA
002 BAC
010 CBA
011 ACB
012 ABC
020 BCA
021 ABC
022 ACB
100 CBA
101 ACB
102 ABC
110 CAB
111 BCA
112 BAC
120 ACB
121 BAC
122 BCA
200 ACB
201 BAC
202 BCA
210 ABC
211 CAB
212 CBA
220 BAC
221 CBA
222 CABDas ergibt folgende Häufigkeiten für die 6 möglichen Permutationen:
ABC: 4/27 ≈ 14.8%
ACB: 5/27 ≈ 18.5%
BAC: 5/27 ≈ 18.5%
BCA: 5/27 ≈ 18.5%
CAB: 4/27 ≈ 14.8%
CBA: 4/27 ≈ 14.8%Bei Gleichverteilung müsste jede Permutation mit der Wahrscheinlichkeit 1/6 ≈ 16.7% gezogen werden. Für n = 3 ist der Algorithmus noch recht brauchbar.
n = 4:
ABCD: 10/256 ≈ 3.9%
ABDC: 10/256 ≈ 3.9%
ACBD: 10/256 ≈ 3.9%
ACDB: 14/256 ≈ 5.5%
ADBC: 11/256 ≈ 4.3%
ADCB: 9/256 ≈ 3.5%
BACD: 10/256 ≈ 3.9%
BADC: 15/256 ≈ 5.9%
BCAD: 14/256 ≈ 5.5%
BCDA: 14/256 ≈ 5.5%
BDAC: 11/256 ≈ 4.3%
BDCA: 11/256 ≈ 4.3%
CABD: 11/256 ≈ 4.3%
CADB: 11/256 ≈ 4.3%
CBAD: 9/256 ≈ 3.5%
CBDA: 11/256 ≈ 4.3%
CDAB: 11/256 ≈ 4.3%
CDBA: 10/256 ≈ 3.9%
DABC: 8/256 ≈ 3.1%
DACB: 9/256 ≈ 3.5%
DBAC: 9/256 ≈ 3.5%
DBCA: 8/256 ≈ 3.1%
DCAB: 10/256 ≈ 3.9%
DCBA: 10/256 ≈ 3.9%bei Gleichverteilung: 1/24 ≈ 4.2%
Die Permutation BADC ist fast doppelt so wahrscheinlich wie DABC und DBCA. Aber es wird schlimmer:
n = 5
(Auszug)
BADEC: 47/3125 ≈ 1.5%
BCAED: 47/3125 ≈ 1.5%
EABCD: 16/3125 ≈ 0.5%bei Gleichverteilung: 1/120 ≈ 0.8%
BADEC und BCAED treten mit fast dreimal so hoher Wahrscheinlichkeit auf wie EABCD. Aber damit nicht genug:
n = 6
min. rel. Häufigkeit: 0/46656 = 0
max. rel. Häufigkeit: 1080/46656 ≈ 2.3%bei Gleichverteilung: 1/720 ≈ 0.14%
Es sind 6! = 720 Permutationen möglich. Der Algorithmus gibt aber nur 120 von diesen aus, die restlichen 600 kommen gar nicht vor!
Ich würd sagen, der Algorithmus ist unbrauchbar.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)-
Hello out there!
Der dort vorgestellte Algorithmus ist ziemlicher Mist. Von einem solchen Algorithmus sollte man doch erwarten, dass er alle möglichen Permutationen mit gleicher Wahrscheinlichkeit ausgibt. Das kann dieser Algorithmus (für Anzahl der Elemente n > 2) gar nicht leisten. (Den Beweis spare ich mir für ein separates Posting auf.)
Wird hiermit nachgeholt:
Sei n die Anzahl der Elemente, n > 2.
Der Algorithmus zieht n mal eine aus n Zufallszahlen; dafür gibt es also nⁿ Möglichkeiten. Anhand der einen Zufallszahlenfolge aus nⁿ möglichen wird eine der n! möglichen Permutationen ausgeben. Es ist nⁿ > n!
Damit alle Permutationen gleichwahrscheinlich wären, müsste jede Permutationen durch gleichviele Zufallszahlenfolgen generiert werden. Dazu müsste nⁿ durch n! teilbar sein.
Für ungerades n ist nⁿ ungerade, n! jedoch gerade; nⁿ folglich nicht durch n! teilbar.
Für gerades n = 2k sei p die größte in n und damit auch in nⁿ enthaltene Primzahl; es ist p ≤ k. Nach dem Bertrandschem Postulat liegt zwischen k und 2k = n eine Primzahl q. Diese ist als Faktor in n! enthalten. Da q > p, kann nⁿ nicht durch n! teilbar sein.
Der Algorithmus erzeugt folglich bei keinem n > 2 eine Gleichverteilung aller Permutationen.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers) -
Ich würd sagen, der Algorithmus ist unbrauchbar.
Aus mathematischer Sicht vielleicht, den Anforderungen des OP jedenfalls scheint er zu genügen, sonst hätte er sich anders geäußert.
Siechfred
--
Hinter den Kulissen passiert viel mehr, als man denkt, aber meistens nicht das, was man denkt.-
Hello out there!
den Anforderungen des OP jedenfalls scheint er zu genügen
Der Ausspruch eines N00bies „hab ich im Netz gefunden und es funzt“ ist selten ein Qualitätsmerkmal.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)-
den Anforderungen des OP jedenfalls scheint er zu genügen
Der Ausspruch eines N00bies „hab ich im Netz gefunden und es funzt“ ist selten ein Qualitätsmerkmal.Danke für die Blumen.
Siechfred
--
Hinter den Kulissen passiert viel mehr, als man denkt, aber meistens nicht das, was man denkt.-
Hello out there!
Ich würd sagen, der Algorithmus ist unbrauchbar.
den Anforderungen des OP jedenfalls scheint er zu genügen
Der Ausspruch eines N00bies „hab ich im Netz gefunden und es funzt“ ist selten ein Qualitätsmerkmal.
Danke für die Blumen.Die waren nicht für dich. Dass mit N00bie nicht du gemeint warst, sollte doch klar sein.
See ya up the road,
GunnarPS: Wie würdest du einen Algorithmus nennen, der vorgibt, ein Zufallsgenerator zu sein, aber mit 98%iger Wahrscheinlichkeit 0.1 augibt, mit 2%iger Wahrscheinlichkeit 0.2, alle anderen Zahlen niemals?
Das ist jetzt etwas überspitzt, aber im Prinzip tut der verunglückte ArrayShuffle-Algorithmus das.
--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)
-
-
-
-
-
-
Hallo David,
Du darfst nicht jede Zufallszahl direkt ins Array speichern, sondern mußt schauen, ob es den Wert schon gibt. Eine Methode inArray() gibt es nicht, kann aber "nachgebaut" werden. In einer Schleife lässt Du nun die Zufallswerte ermitteln und prüfst, ob der Wert schon dabei war. Ist er neu, fügst Du diesen hinzu. Das ganze machst Du solange, bis die gewünschte Array-Länge erreicht ist
Array.prototype.inArray = function(val){ for (var i=0; i<this.length; i++) if (typeof(this[i]) == "object"){ return this[i].inArray(val); } else if (this[i] == val) return true; return false; } var zahlen = []; do { var bla=Math.round(Math.random()*mitglieder+1); if (!zahlen.inArray( bla )) zahlen.push( bla ); while (zahlen.length < mitglieder)Mit freundlichem Gruß
Micha-
Hallo Micha,
Du darfst nicht jede Zufallszahl direkt ins Array speichern, sondern mußt schauen, ob es den Wert schon gibt. Eine Methode inArray() gibt es nicht, kann aber "nachgebaut" werden.
Das ist ist im Prinzip richtig, aber der Vorschlag zur Umsetzung ist etwas umständlich und hat Mängel.
Z.B. folgender rekursive Aufrufif (typeof(this[i]) == "object"){
return this[i].inArray(val);
}funktioniert nur, wenn ein Arrayelement wiederum ein Array ist. Wenn es aber ein anderes Objekt ist, ergibt `this[i].inArray(val)`{:.language-javascript} einen Fehler. [Gunnar hat inzwischen auch darauf hingewiesen](https://forum.selfhtml.org/?t=163655&m=1065894), dass man statt `Math.round`{:.language-javascript} besser `Math.floor`{:.language-javascript} benutzen sollte, um zufälligere Ergebnisse zu erhalten. Folgendende Methode .shuffle() arbeitet besser: ~~~javascript Array.prototype.shuffle = function() { if (!this.length) {return;} var r, rA = new Array(this.length); do { do { r = Math.floor(Math.random() * rA.length); // neue ganze Zufallszahl (0...Anzahl Elemente) } while (typeof rA[r] !== 'undefined'); // solange die Zahl schon gezogen wurde rA[r] = this.pop(); } while (this.length); do{ this.push(rA.pop()); } while (rA.length); };Hier hat man einen der wenigen Fälle, wo es Sinn macht, die Arraylänge schon bei der Deklaration anzugeben.
Gruß, Don P
-
-
Grütze .. äh ... Grüße!
Hallo zusammen,
brauch ein Script das mit wenn man sagen wir mal 14Mitglieder hat, 14 verschiedene Zahlen ausgibt als Zufallsausgabe. Die Ausgabe klappt, aber sind immer noch doppelte dadrin. Hab den Krempel mal in ein Array gestopft, aber wie kann ich das machen, dass ich das vergleiche oder der mit 14 Zahlen ausgibt ohen DOPPELTE.
Zum Beispiel so:
Lösche den jeweils ausgewählten Eintrag mit splice (Achtung: erst ab IE5.5, ansonsten gibt es Funktionen, die diese Funktion nachbauen)aus dem Array und starte den neuen Zufallswert wieder mit einem um 1 verringerten Maximalwert. (hier bietet es sich an, mit der length-Eigenschaft des Array zu arbeiten, die ja beim Löschen automatisch reduziert wird)Cü
Kai--
What is the difference between Scientology and Microsoft? One is an
evil cult bent on world domination and the other was begun by L. Ron
Hubbard.
ie:{ fl:( br:< va:) ls:? fo:| rl:? n4:° ss:{ de:] js:| ch:? mo:| zu:| -
Hello out there!
var bla=Math.round(Math.random()*mitglieder+1);
Math.round() ist in den allermeisten Fällen in Verbindung mit Math.random() falsch. [http://forum.de.selfhtml.org/archiv/2006/7/t132358/#m856490]
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)