Prinzipieller Ansatz für den "Lotto"-Problem-Algoritmus

[Zvoni]

Hallo alle,

nachdem ich in letzter Zeit öfters mal Threads gesehen habe (nicht nur hier bei Tutorials), wo Leute um Hilfe beim berühmt-berüchtigten "Lotto"-Problem bitten (x Zufallszahlen aus n Möglichen ohne doppelte Werte), habe ich mir mal das ganze Ding durch den Kopf gehen lassen (Keine Angst, ich blute nicht aus den Ohren ^^).

Mal ganz unabhängig von der verwendeten Sprache, bin ich auf folgende Idee gekommen, und wollte mal eure Meinung dazu wissen:

Algoritmus:

1) Bilde ein sortiertes Array für die n Möglichen Zahlen in der Form:
arrLotto(1)=1
arrLotto(2)=2
.
.
arrLotto(19)=19
.
.
arrLotto(49)=49
usw.

2) Hier setzt meine Idee an (btw: vielleicht ist ja meine Idee ja gar nicht so neu, aber ich habs bisher nirgends gesehen): Benutze einen Misch-Algoritmus (gibts sicher im Netz, im Prinzip das Gegenteil zu Quicksort), der die Werte des obigen Arrays durcheinander wirft. Das Ergebnis sieht dann in etwa wie folgt aus:
arrLotto(1)=17
arrLotto(2)=31
arrLotto(3)=5
usw.

3) Um jetzt beim klassischen Lotto zu bleiben (6 aus 49), würde es vollkommen ausreichen, die Werte aus den ersten 6 Elementen des Arrays auszulesen.

Ich habe in einem VB-Buch die Beschreibung eines Misch-Algoritmus gelesen, der wie folgt beschrieben wird:

The algorithm works by choosing any random element between the first and last elements and exchanging it with the last element, which then is random. Next it finds a random element between the first and the next-to-last elements and exchanges it with the next-to-last element. This process continues until the shuffling is finished.

Wenn ich das richtig verstanden habe, würde bei meiner Variante, im Gegensatz zur klassischen Lösungsvariante, welche ja die Zufallszahlen erzeugt, und dann prüft, ob diese bereits "gezogen" wurde, eben genau diese Prüfung entfallen, ob eine Zahl bereits gezogen wurde. Bei "6 aus 49" macht das an Speed sicher nicht viel aus, aber wie siehts bei "20.000 aus 1 Mio" aus?

Meinungen dazu?

 

[Wolfsbein]

Du tauschst im Prinzip nur Geschwindigkeit gegen Speicherplatz aus. Solange die Anzahl Zufallszahlen sehr gering im Vergleich zum Wertebereich ist, wird die herkoemmliche Variante (fast) genau so schnell sein. Sonst deine.

 

[Zvoni]

Speed für Memory ist mir klar, aber wenn ich mal vom Beispiel "20K aus 1M" ausgehe, dann ist die Speicherreservierung für die 1M Werte gerade mal 4MB (mal von 32-Bit-Integern ausgehend) plus einem eventuellen Overhead.

Im Zeitalter von Maschinen mit im Schnitt 1GB RAM sehe ich da eigentlich eher das geringere Problem.

EDIT: Mir ist nachträglich noch etwas eingefallen: Bei der "klassischen" Variante besteht die Möglichkeit (so unwahrscheinlich sie auch sein mag) in einer Endlosschleife hängen zu bleiben!

 

[hela]

... Bei der "klassischen" Variante besteht die Möglichkeit (so unwahrscheinlich sie auch sein mag) in einer Endlosschleife hängen zu bleiben!

Hallo Zvoni,
hängenbleiben kann man immer und überall.

Beim Misch-Algorithmus musst du (z.B. beim 6aus49-Spiel) 49 mal eine Zufallszahl bilden, bei der "klassischen Variante" nur 6 mal und hast dann aber noch den Ergebnisvergleich .
Wahrscheinlich muss man es ausprobieren, welche Variante am besten ist.

 

[Zvoni]

Hallo Zvoni,
hängenbleiben kann man immer und überall.

Yoaa, weiss ich auch (speziell letzte Woche, als ich im Türrahmen hängengelieben bin, das lag jedoch wohl eher an dem letzten Tequila um halb 2 nachts) ^^

Beim Misch-Algorithmus musst du (z.B. beim 6aus49-Spiel) 49 mal eine Zufallszahl bilden, bei der "klassischen Variante" nur 6 mal und hast dann aber noch den Ergebnisvergleich .
Wahrscheinlich muss man es ausprobieren, welche Variante am besten ist.

Eben nicht. Der Teufel kann es wollen, dass die ersten Zufallszahlen passen, und eine folgende Zufallszahl aber eine ist, welche in den ersten Ziehungen bereits gezogen wurde. Und eben hier (so unwahrscheinlich es eben auch sein mag, aber die Wahrscheinlichkeit ist eben definitiv grösser 0) steckt die Gefahr, in einer Endlosschleife stecken zu bleiben.
Beim Misch-Algoritmus besteht diese Gefahr eben nicht.

 

[Navy]

Nein. Eine Endlosschleife entsteht dann, wenn eine Schleife unter keinen Umständen terminiert. Im Falle des Suchen von Zufallszahlen die noch nicht bekannt sind, kann sie Laufzeit zwar lang werden, die Wahrscheinlichkeit, dass sie jedoch unendlich ist, ist genau 0.

Effektiv wäre es, eine Liste aufzubauen, die alle n Werte beinhaltet und darüber eine Schleife mit p Durchläufen laufen zu lassen, die im Durchlauf einen Zufallswert m zwischen 1 und n erstellt, die Zahl an m-ter Stelle aus der Liste in eine zweite Liste verschiebt und n um eins vermindert. Dadurch hätte man keinerlei Überprüfungen, ob die Zahl bereits vorhanden ist, noch müsste die Liste mit x Durchläufen vermischt werden. Im schlimmsten Fall hätten wir dann m * n - ( m * ( m + 1 ) ) / 2 Indexdurchläufe in der Liste, was aber bei Zugriffen auf Arrays im gleichen Fall ebenso läuft.

 

[Zvoni]

hmmm, die Variante hat auch Charme. Jetzt müsste man nur noch den Overhead herausbekommen für das kopieren und ausschneiden.

Zum Thema Endlosschleife: Bist du dir sicher, dass die Wahrscheinlichkeit, dass bei 6aus49 unendlich mal hintereinander die Zahl 12 gezogen werden kann, gleich 0 ist? Mich interessiert es vom folgenden Standpunkt aus: Die Mathematik sagt klar, dass die Wahrscheinlichkeit hierfür grösser 0 ist (oder liege ich da falsch? Abitur ist bei mir 19 Jahre her ^^).

 

[Navy]

Berechne doch einfach mal den Limes von x^n, n gegen unendlich, mit x Element der reellen Zahlen und 0<x<1. (Meinetwegen mit x=48/49).

Der Verwaltungsoverhead wäre sehr klein, da pro Bewegungsoperation genau 2 Pointer umgebogen werden müssen.

 

[Klein0r]

Mal ne ganz andere Frage: Mit wieviel Millionen Seitenaufrufen pro Sekunde rechnest du das es dir um die paar Millisekunden geht?

Es gibt immer viele Lösungen... Aber deine finde ich irgendwie unklug gelöst. Wenn ich das später so sehen würde, würde ich denken: "Da hat sich aber jemand keine Gedanken gemacht".

Und das der Algor. in ner Endlosschleife endet is so wahrscheinlich wie die Aussage das theoretisch schon nächstes Jahr die erste Stadt auf dem Mars erbaut wird. Sicher kann das ganze "ein wenig länger" dauern (lass es 1000 Durchläufe sein), aber das würde man trotzdem nicht merken...

Und@erster Post: Der erste Arrayindex ist 0 und nicht 1

lg

 

[Mark]

Hi!

Bitte nicht erschlagen, wenn es totaler Blödsinn ist, aber ich habe obiges Thema interessiert verfolgt (ich mag Algorithmen ) und kam auf folgende "Idee" ... bei der ich allerdings bereits bei den Anfängen mathematisch scheitere

Man zieht eine Zufallszahl zwischen 1 und 10.068.347.520 (49x48x47x46x45x44 ?!) und hat sofort eine komplette Ziehung!
Wie nun die Umwandlung dieser Zahl in die sechs Ziehungs-Zahlen funktionieren könnte (es böte sich ja beinahe das binäre System an: 49 Stellig mit 6 Einsen, aber die Zahlen müssten sich ja auf die beschränken, die genau 6 Einser beinhalten ) weiß ich nicht...
... nur mal als Ansatz, nicht als praktikable Alternative

Liebe Grüße,
Mark.

//edit: @Klein0r: ich dachte, es geht hier um eine grundsätzliche "Lotto-Lösung" und keine konkrete "Website" ... siehe ganz oben...?