nicht angemeldet
Eine Reihe von Zufallszahlen ohne Redundanz
Hallo liebe Poster und Helfer,
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.
Kann man mir helfen ??
d.grimmer
-
Hi,
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.sprich: Du möchtest ein Array, dessen Elemente ihren jeweiligen Index beinhalten, zufällig sortieren.
Kann man mir helfen ??
Hilft Dir diese andere Betrachtungsweise? :-) Wenn nicht: Denk Dir einfach zwei Arrays. Das eine ist zu Beginn sortiert gefüllt, das andere ist leer. Jetzt holst Du aus dem sortierten nacheinander zufällige Elemente raus, die Du dem anderen Array hinzufügst, bis das erste leer ist.
Cheatah
-
Hi,
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.sprich: Du möchtest ein Array, dessen Elemente ihren jeweiligen
Index beinhalten, zufällig sortieren.
Kann man mir helfen ??
Hilft Dir diese andere Betrachtungsweise? :-) Wenn nicht:
Denk Dir einfach zwei Arrays. Das eine ist zu Beginn sortiert
gefüllt, das andere ist leer. Jetzt holst Du aus dem sortierten
nacheinander zufällige Elemente raus, die Du dem anderen Array
hinzufügst, bis das erste leer ist.Cheatah
An dem Punkt stehe ich auch gerade.
Leider Funktioniert das Löschen eines zufällig ausgewählten Elementes
meines Wissens nach nur, solange es das Erste oder Letzte ist !?
Es gibt kein "Delete".
Einzig "slice" käme als Methode in Frage?? aber der Rückgabewert ist
eben das eine Element !?-
Hi,
Einzig "slice" käme als Methode in Frage?? aber der Rückgabewert ist
eben das eine Element !?na, freu Dich. Genau das willst Du doch haben.
Cheatah
-
-
-
Hallo liebe Poster und Helfer,
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.
Kann man mir helfen ??d.grimmer
Hi d(e).grimmer
naja, Zufall ist halt Zufall. Wenn ein Zufallswert von gewissen Vorbedingungen abhängig ist, ist es kein wirklicher Zufallswert mehr. Dein 60. (= letzter) Wert hat dann z. B. überhaupt nichts mehr mit Zufall zu tun. Tipp: Zufallswert plus Nachbearbeitung. Zufallswert ermitteln und nachsehen, ob diese Zahl schon gezogen wurde. Falls ja: verwerfen, falls nein: nehmen. Nicht die eleganteste oder gar laufzeitoptimierte Methode, aber einfach in der Implementierung.
Ciao
Hans-Peter-
Hi,
naja, Zufall ist halt Zufall. [...] Zufallswert ermitteln und nachsehen, ob diese Zahl schon gezogen wurde. Falls ja: verwerfen, falls nein: nehmen.
dieser Algorithmus ist nicht terministisch. Was ist, wenn der letzte noch fehlende Wert per Zufall (denn genau das ist es) nie gezogen wird?
Cheatah
-
Auch hi,
dieser Algorithmus ist nicht terministisch. Was ist, wenn der letzte noch fehlende Wert per Zufall (denn genau das ist es) nie gezogen wird?
na ja wie gesagt: Der Algorithmus ist nicht laufzeitoptimiert :-) Aber der letzte Wert _wird_ gezogen. Immerhin unterliegt der letzte Wert genau der gleichen Wahrscheinlichkeit wie alle anderen Werte. Es kommt halt drauf an, ob da ein Client / ein Besucher auf das Ergebnis warten muß, oder ob es wirklich völlig egal ist, wie lange die Berechnung dauert. Meine Lösung ist nicht genial, sie ist trivial (bestenfalls genial einfach).
Hans-Peter
-
Hi,
na ja wie gesagt: Der Algorithmus ist nicht laufzeitoptimiert :-)
stimmt :-)
Aber der letzte Wert _wird_ gezogen. Immerhin unterliegt der letzte Wert genau der gleichen Wahrscheinlichkeit wie alle anderen Werte.
Ja: 1/60. Die Wahrscheinlichkeit, bei n Ziehungen diesen Wert zu erhalten, beträgt _nicht_ n*1/60. Die Formel habe ich leider nicht mehr im Kopf (1-(1-1/60)^n?); aber nach n Versuchen ist die Wahrscheinlichkeit noch immer kleiner als 1. Der Fall "wird nicht gezogen" _kann_ vorkommen.
Es kommt halt drauf an, ob da ein Client / ein Besucher auf das Ergebnis warten muß, oder ob es wirklich völlig egal ist, wie lange die Berechnung dauert.
Die Wartezeit kann ins Unendliche gehen. Wenn ein Versuch eine Millisekunde dauert, ist _jede_ Millisekunde die Wahrscheinlichkeit wieder 59/60, dass die richtige Zahl _nicht_ gefunden wird. Auf Dauer gesehen ist es zwar unwahrscheinlich; aber es ist _nicht_ zwingend gegeben, dass der Algorithmus terminiert.
Und bedenke bitte: Das Problem tritt nicht erst beim letzten Wert auf, sondern bereits beim zweiten.
Cheatah
-
Hallo Cheatah,
Ja: 1/60. Die Wahrscheinlichkeit, bei n Ziehungen diesen Wert zu erhalten, beträgt _nicht_ n*1/60. Die Formel habe ich leider nicht mehr im Kopf (1-(1-1/60)^n?); aber nach n Versuchen ist die Wahrscheinlichkeit noch immer kleiner als 1. Der Fall "wird nicht gezogen" _kann_ vorkommen.
So ein aehnliches Problem haben wir hier auch an einer Stelle. Auf der Download-Seite von SELFHTML werden ja bei jedem Aufruf immer 10 andere Adressen angeboten. Dazu muessen alle verfuegbaren Adressen eingelesen werden. 10 davon sollen per Zufall eingelesen werden. Dabei soll der Algorithmus aber so wasserdicht sein, dass er auch dann sauber arbeitet, wenn nur 10 Adressen als Ressource zur Verfuegung stehen, also alle verfuegbaren Adressen aufgelistet werden muessen, nur in beliebiger Reihenfolge. Christian hat dazu folgende Perl-Zeile produziert:
push @new, splice(@resource_lines, rand @resource_lines, 1) while (@resource_lines && @new < 10);
In @resource_lines sind die zeilenweise eingelesenen Adressen gespeichert. In @new soll der Array der 10 aufzulistenden Adressen erzeugt werden.
while (@resource_lines && @new < 10)
sorgt dafuer, dass @new so lange gefuettert wird, bis 10 Eintraege vorhanden sind oder keine eingelesenen Adressen mehr verfuegbar sind.Solange wird @new mit push etwas hinzugefuegt, und zwar der Rueckgabewert der splice-Funktion. So, wie splice dort mit Parametern versorgt wird, wird einfach ein zufaellig ausgewaehltes Element aus @resource_lines geloescht. Da splice das geloeschte Element zurueckgibt, ist dies ein brauchbarer zweiter Parameter fuer push. Da das verwendete Element gleichzeitig geloescht wird, ist beim naechsten Schleifendurchgang sichergestellt, dass es nicht mehr da ist (und also in der Ergebnisliste @new nicht doppelt auftauchen kann).
Mit dieser Technik kann man finde ich Probleme der geschilderten Art ganz gut loesen.
viele Gruesse
Stefan Muenz-
Hi Stefan,
Christian hat dazu folgende Perl-Zeile produziert:
Christian, gib's zu - Du hast aus perldoc perlfaq4 geklaut ;-) (Und das ist gut so... dazu ist es schließlich da!)
push @new, splice(@resource_lines, rand @resource_lines, 1) while (@resource_lines && @new < 10);
Jupp. Genau dies, nur in extrem performanter Form, ist es, was ich vorgeschlagen habe: Solange zufällige Werte aus dem (leicht generierbaren) ursprünglichen Array nehmen und dem anschließend zufällig sortierten hinzufügen, bis das erste leer und das zweite voll ist. In JavaScript ist das vermutlich(?) nicht ganz so geschickt zu lösen; aber grundsätzlich ist der Algorithmus der gleiche.
Cheatah
-
Hallo Cheatah,
Christian hat dazu folgende Perl-Zeile produziert:
Christian, gib's zu - Du hast aus perldoc perlfaq4 geklaut ;-)
Nein, aus einem Algorithmen-Buch ;-)
push @new, splice(@resource_lines, rand @resource_lines, 1) while
(@resource_lines && @new < 10);Jupp. Genau dies, nur in extrem performanter Form,
Ja, die Performance ist hier in der Tat leider ein Problem: durch das
splice() wird der Algorithmus sehr langsam. Da ist deine
Implementierung wesentlich schneller, aber an dieser Stelle (dem
Download-Script) war es relativ egal, ob das nun ein paar Ms schneller
oder langsamer lief.Gruesse,
CK
-
-
-
-
-
-
»»Tipp: Zufallswert plus Nachbearbeitung. Zufallswert ermitteln und nachsehen, ob diese Zahl schon gezogen wurde. Falls ja: verwerfen, falls nein: nehmen.
Hi,
nicht ganz (verwerfen), sondern einfach den nächsten freien nehmen.
Auf diese Weise ist man nach 60 Schritten garantiert durch...Bye
Wolfgang-
Hi Wolfgang,
Tipp: Zufallswert plus Nachbearbeitung.
Zufallswert ermitteln und nachsehen, ob
diese Zahl schon gezogen wurde. Falls ja:
verwerfen, falls nein: nehmen.
Hi,
nicht ganz (verwerfen), sondern einfach den
nächsten freien nehmen.
Auf diese Weise ist man nach 60 Schritten garantiert
durch...... und hat garantiert keine Gleichverteilung mehr.
Notwendige Voraussetzung für die Gleichverteilung ist die Unabhängigkeit der Zufallsereignisse.
Deine Änderung jedoch macht die sofortige Ziehung von Zahlen direkt hinter großen Lücken wahrscheinlicher als diejenige von deren direktem Nachfolger.
So geht es also nicht ...
Viele Grüße
Michael
-
-
-
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.
Kann man mir helfen ??Hi again,
also gut. Noch´n Versuch, nachdem mein erster Algorithmus bei Cheatah (unverständlicherweise) in Ungnade gefallen ist:
step 1: ein Source-Array mit 60 Elementen erzeugen, jedes Element wird mit seinem Index gefüllt.
step 2: ein Destin-Array mit 60 Elementen erzeugen und uninitialisiert lassen.
step 3: mittels Math.random()*60 eine (Integer-) Zufallszahl zwischen 0 und 59 erzeugen das Ergebnis ist der Index in die Source-Tabelle. Der Wert des so selektierten Source-Array Elemtes ist der erste Wert für das Destin-Array.
step 4a: Alle Elemente des Source-Array, beginnend mit dem ersten Wert _nach_ dem selektierten Element bis zum Ende des Arrays alle Elemente um eine Position nach vorne schieben. Der Wert des selektierten Elementes wird so eliminiert, die Tabelle wird ein Element kürzer.step 3 wiederholen, jedoch (mittels Math.random() * 59) eine Zufallszahl in einem nun kleineren Bereich erzeugen und damit das Source-Array referenzieren.
step 4 wiederholen. Das zweite Destin-Array Element wird generiert, das Source-Array wird wieder kürzerstep 3 und 4 so lange wiederholen, bis Source-Array kein Element und Destin-Array 60 Elemente enthält
okay Cheatah ?
Ciao
Hans-peter-
Hallo,
also gut. Noch´n Versuch, nachdem mein erster Algorithmus bei
Cheatah (unverständlicherweise) in Ungnade gefallen ist:[...]
Das ist doch derselbe Algorithmus, den Cheatah beschrieben hatte ;-)
Gruesse,
CK-
Hallo Christian
Das ist doch derselbe Algorithmus, den Cheatah beschrieben hatte ;-)
ääh ... ja. Stimmt. Jetzt wo´s Du´s sagst ...
Hans-Peter
-
-
-
Hi,
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.
Kann man mir helfen ??bei den bisherigen Antworten fällt mir auf, das kein Hinweis auf die mangelhafte Implementation der Zufälligkeitsfunktion von javascript erfolgt ist.
Ein Algorythmus, der auf Math.random aufbaut, arbeitet nicht einwandfrei. Ab mehr als 16 Einträgen in einem Array kommt es sporadisch zu Aussetzern in der Generierung des Zufallswertes.
In früheren Diskussionen wurde gerne darauf hin gewiesen.
Beispiel: http://www.jelue.de/lotto_neu.htm
Das Beispiel arbeitet mit 49 Einträgen im Array. Nach mehrmaligem Ausführen kommt es zu Problemen und die Logik versagt, weil kein gültiger Zufallswert erzeugt wurde. Beobachtet unter Netscape6.2 und IE ab 5.5.
Von daher kommt es sehr auf den verfolgten Zweck an, ob man solch eine Funktionalität in eine Webseite einbaut.
Gruß
Günter -
Ich möchte ein Array mit 60 Elementen mit
60 Zufallszahlen zwischen 0 und 59 , ohne redundante
Werte erzeugen.
Kann man mir helfen ??