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

[Klein0r]

Wow das ist nun sehr Tiefgründig...

Keine Ahnung ob man das wirklich so rechnen darf. Aber die Idee ist wirklich.... außergewöhnlich Gefällt mir zumindest besser als die Array-geschichte

Allerdings ist deine Zahl binär gerade mal:
1001011000000111101100101010000000

Und das in 6 Parts aufgeteilt wird nicht gehen da es 35 Zeichen sind.
Auch wenn es 36 Zeichen wären und ein Part aus 6 Bits besteht würde es nicht ganz aufgehen da binär 111111 = dezimal 63 sind und nicht 49

Aber mit einem Zahlensystem auf der Basis 49 könnte gehen
Glaube ich zwar auch nicht wirklich aber naja

lg

 

[Navy]

Die Idee ist prinzipiell nicht schlecht, das die Details könnten hier jedoch Probleme bereiten. Bei 13.983.816 Möglichkeiten ist das Binär 00110101010110000001001000, was man dann in 6 Zahlen aufteilen muss, es aber keine Basis für die 49 gibt und ein Tupel nicht zwangsläufig einmalig vorkommt.

Du müsstest also einen Algorithmus schreiben, der jeder Zahlenkombination eine eineindeutige Abbildung auf die 13.983.816 Möglichkeiten definiert und das wäre dann wohl nicht mehr effizient...

 

[Zvoni]

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.

Örrkss, Was ist ein Limes? Ich kenne Limes nur als römischen Grenzwall ^^

@mark
Woaaahh, die Idee hat nun wirklich mal was.

nur der Ansatz ist glaub ich falsch.
Muss ich mir mal durch den Kopf gehen lassen (am besten noch mit nem Pils gewürzt - kann ich besser denken^^)

 

[Zvoni]

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

@klinOr
Hehe, in VB kann ich aber sagen, wo ein Array beginnt, und ich lasse es eben bei 1 beginnen ^^

 

[hela]

... Eben nicht. Der Teufel kann es wollen, dass die ersten Zufallszahlen passen, und eine folgende Zufallszahl ...

Hallo Zvoni,
zu den Gütekriterien eines gewöhnlichen Zufallsgenerators gehört, dass die ausgegebenen Werte (möglichst) gleichverteilt sind und dass die Autokorrelationsfunktion größer Null (möglichst) verschwindet.
Letzteres schließt solche Möglichkeit, die du da beschreibst, eben aus. Ansonsten liefert dieser "Zufallszahlengenerator" eben keine Zufallszahlen mehr.

 

[Zvoni]

OK, zum Thema Endlosschleife glaub ich es euch einfach mal, dass es nicht passiert, aber zur Idee von mark:

Man nehme einen Algoritmus, der mir alle Tupel erstellt die möglich sind (13.983.816 Stück).
Diese Tupel speichere ich in einer Datei (Datenbank?) ab. Ich stelle das ganze mal dar, wie ich es in VB machen würde:

Private Type UDTTupel   'In C/C++ heisst das hier glaube ich Structur
Zahl1 as Long         'Long ist in VB 32-Bit-Integer, bei 6aus49 könnte man auch Byte nehmen
Zahl2 as Long
Zahl3 as Long
Zahl4 as Long
Zahl5 as Long
Zahl6 as Long
End Type

Dim Tupel as UDTTupel

'Algoritmus, der mir alle Tupel erstellt
'Schleife, der mir alle Tupel in die Datei schreibt per Random-Access
For i=1 to 13983816
'Hier Code für "Erstelle i-tes Tupel"
put#Datei,i,Tupel  'Schreibe Tupel in Datei in Zeile i
Next
Close#Datei  'Datei schliessen

'Hier Code für eine einzige Zufallszahl zwischen 1 und 13.983.816
Open MeinPfad & "\Tupel.dat" For Random as #Datei Len=Len(Tupel)  'Datei im Random-Access-Mode öffnen

Get#Datei,Zufallszahl,Tupel   'Hole das Tupel an der Zufallszahl-ten Stelle aus der Datei

Diskussion: Mir ist klar, dass ich eine 335.611.584 Byte (~335MB) grosse Datei erstelle, aber bei der ganzen Geschichte hier geht es ja erstmal nur ums Prinzip.^^
Mit dieser Variante hätten wir mark's Idee zumindest irgendwie umgesetzt:
1 Zufallszahl=1 komplette Ziehung.

Die Datei muss nur ein einzigstes Mal erstellt werden.

Meinungen?

 

[Navy]

Was Du machst (bzw. machen möchtest) ist nichts anderes als ein Abspeichern aller möglichen Permutationen. Das ist nicht sonderlich effizient, jedoch ab einer bestimmten Menge an Kombinationsabfragen die schnellste Variante -- sofern das Auslesen aus der Datei hinreichend schnell geschieht.

Dennoch bin ich kein Freund solcher Methoden, da sie die "weiche Vorschlaghammermethode" darstellt und es weitaus effizientere (und vor allem generische) Methoden gibt.

 

[Klein0r]

Also das mit der Datei ist sicher möglich - aber halte ich für absolut schwachsinnig.

Wenn du die aktuelle Uhrzeit anzeigen willst speicherst du ja auch nicht alle Daten von 1900 bis 2300 und schiebst per Crontab jeden Tag nen Zeiger einen Eintrag weiter.

Bin auf die nächsten Lösungen gespannt
Mann könnte auch eine Engine für einen Shooter schreiben - dazu dann ein einfaches Game in dem ein Bot auf eine Wand aus 13.983.816 Polygonen schießt. Je nach dem welches Polygon er trifft hast du eine andere Zahl. Leider braucht der Bot auch Zufallswerte die generiert werden müssten... Wobei wir wieder beim alten Problem wären

Also langsam....
340 mb Speicherplatz für 6 Zufallszahlen... ehrlich cool

lg

 

[Zvoni]

Dennoch bin ich kein Freund solcher Methoden, da sie die "weiche Vorschlaghammermethode" darstellt und es weitaus effizientere (und vor allem generische) Methoden gibt.

Es geht doch hier erstmal ums Prinzip ^^

Bin auf die nächsten Lösungen gespannt

Genau um das gehts in diesem Thread ^^

Also langsam....
340 mb Speicherplatz für 6 Zufallszahlen... ehrlich cool

lg

hmm, vielleicht bekommen wir für "20.000aus1.000.000" den SETI-Rechner^^

 

[Zvoni]

Also, ich hab mal über Navy's Ansatz nachgedacht, und das ganze Ding mal in VB-Classic umgesetzt.

Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)

Sub Lotto(ByVal Anzahl As Long, ByVal Aus As Long)
Dim arrQuelle() As Long     'Leeres Array erzeugen
Dim arrZiel() As Long

'Hilfsvariablen
Dim i As Long
Dim j As Long
Dim Treffer As Long
Dim Zufall As Long

    'Festlegen der "Spielvariante" - Bsp. 6 aus 49
    ReDim arrZiel(1 To Anzahl)
    ReDim arrQuelle(1 To Aus)
    
    'Erstellen Urmenge
    For i = 1 To Aus
    
        arrQuelle(i) = i
    
    Next
    
    Treffer = 0
    
    Do
    
        Randomize
        
        'Ubound = Funktion zum Ermitteln der oberen Array-Grenze
        Zufall = Int(UBound(arrQuelle) * Rnd + 1)
    
        Treffer = Treffer + 1
        arrZiel(Treffer) = arrQuelle(Zufall)
        
        'Ausschneiden der bereits gezogenen Zahl aus dem Quell-Array
        For j = Zufall + 1 To UBound(arrQuelle)
        
            CopyMemory arrQuelle(j - 1), arrQuelle(j), 4
            
        Next
        
        'Verkleinern des Quell-Arrays um 1
        ReDim Preserve arrQuelle(1 To UBound(arrQuelle) - 1)
           
    Loop Until Treffer = Anzahl

End Sub

'Aufruf dann mit
Lotto 6, 49