Logikfehlersuche, das perfekte Lottosystem für 3 Richtige mit Arraylists?

berndoa

Top Contributor
Hallo, ich hoffe ich darf das in dem Unterforum posten. Ich habe was programmiert.

Hintergründe des Ganzen sind lottosysteme und die Suche nach dem "perfekten(sprich:minimalen) System" mit dem man garantiert 3 Richtige hat.

Hierzu will ich hingehen, habe ein System vorgegeben von dem ich weiß dass es 3 Richtige bringt. und werfe es in eine Funktion die versucht nacheinander immer wieder eine überflüssige Tippreihe rauszuwerfen (sodass das neue verkürzte System aber immer noch 3 Richtige garantiert).
Was dann übrig bleibt, sollte ein System sein, das immer noch 3 Richtige garantiert wenn man alle Tippreihen gleichzeitig spielt.
Bei dem man aber auch keine der Tippreihen weglassen kann ohne dass die 3 Richtige Garantie verletzt wird.

Ein "System" in dem Sinne ist im Übrigen einfach eine Liste von je 6 Lottozahlen.
Programmiertechnisch habe ich dies umgesetzt als Arraylist, die als Elemente wieder eine Arraylist mit long elementen hat.

Ist so der Hintergrund, mir geht aber primär um die Umsetzung des optimierungsalgorithmus.
ich habe also einen initialen input, ein vorgegebenes system dass es zu optimieren gilt.
dann lasse ich von einer methode eine liste aller möglichen 6-tuples erstellen, also liste aller denkbaren 6 gewinnzahlen die beim lotto gezogen werden könnten.

dann teste ich der reihe nahc die zeilen in input dahingehend durch ob man sie weglassen könnte.
falls ja, wird unsere inputliste durch eine neue lsite ohne jene zeile ersetzt.

wann ist eine zeile ersetzbar?
hierzu bilde ich eine kopie der inputliste, in der die j-te zeile fehlt.

mit dieser liste machen ich nun folgendes:
ich gehe der reihe nahc alle lottozahlen durch und vergleiche jede lottozahl mit jeder der zahlen unserer liste.
sagen wir ich habe eine lottozahl, dann vergleiche ich die mit jeder der listenzahlen und merke mir bei jedem mal wie viele richtige die 2 zahlen gemeinsam hatten.
ich gucke, wenn ich die lottozahl mit allen listenzahlen abgeglichen haben, was die höchste menge an richtigen war, die vorkam.

Denn wenn in einer ziehung jene lottozahl gezogen wird und ich hatte alle unserer lsitenzahlen gespielt, dann ist dieses maximum ja gerade die höchste erreichte gewinnklasse.
wir speichern uns also für jede der getesteten lottozahlen jene ermittelte maximal erreichte gewinnklasse.

machen wir für jede lottozahl und speichern es in nem array.
nun gucken wir uns das array an und suchen, dieses mal, das minimum der werte.

denn wir wissen ja nun für jede der lottozahlen was wir für eine gewinnklasse maximal haben wenn wir unser system gespielt hätten.
wenn wir nun das minimum dieser maximalzahlen nehmen, dann wissen wir welche gewinnklasse wir in jedem fall mind. erreicht haben, ganz unabhängig davon welche lottozahlen gezogen werden.

ein paar gedankenschritte zurück:
jene vergleichsliste war ja die ursprüngliche inoputliste abzüglich dem j-ten element (oder element mit index j, genau genommen).
wenn wir nun also als ergebnis finden dass wir mit dieser verkürzten liste mind. 3 richtige haben, können wir happy sein.
denn das heißt wir können in der ursprungslösite die j-te reihe wegfallen lassen ohne dass es unserer 3+richtige garantie schadet.

so gehen wir für unsere initiale input liste der reihe nach alle zeilen durch und sobald wir eine zeile gefunden haben, die wir rauswerfen können und trotzdem unsere qualitätsansprüche erhalten bleiben, sind wir fertig und brauchen auch die restlichen reihen überprüfen.
pro iteration wollen wir ja nur eine reihe finden, die wir rauswerfen können.

sobald also eine passende reihe gefunden ist, sind wir fertig.
dass eine erfolgreiche reihe gefunden und rausgeworfen wurde, gibt uns die optimizefunktion durch einen rückgabewert von 1 an. hat sie hingegen alles durchsucht und ncihts zum optimieren gefunden, gitb sie 0 zurück.

nun optimieren wir immer wieder so lange wie jedes mal eine 1 zurückgegeben wird. wird irgendwann hingegen eine 0 zurückgegeben, wissen wir dass usnere lsite nicht mehr verbessert werden kann und sind fertig.
wir geben die länge der liste und seine elemente just for fun mal nocg auf der konsole aus.


Falls überhaupt jemand bis hierhin gelesen hat:
Meint ihr dass mein unten beigefügter Code das gewünschte erreicht?
Mir ist klar dass er performance mässig vermutlich eine katastrophe ist.
Habt ihr eine gute idee wie man es verbessern könnte?
Habe auch shcopn über andere datentypen nachgedacht, aber ich habe , gerade bei den vielen verschatelungen und was hier so nötig ist, nicht genug ahnung von diesen um da was sinnvolles zu produzieren.
Ob es perfomancemässig besser wäre, weiß ich auch nicht. was meint ihr? :)



Java:
import java.util.*;


public class Test9{
    
    
    public static void main(String[] args){
      ArrayList<ArrayList<Long>> sixtuples=sixtuples();
      ArrayList<ArrayList<Long>> input=args[0];
      
      System.out.println("Mit dem System werden mindestens einmal "+calculate(sixtuples,input)+" Richtige erreicht!!!");
        
        while(optimize(sixtuples,input)>0){
            System.out.println("Optimiert! Das neue System hat noch "+input.size()+" Tippreihen!");
        }
        
        System.out.println("Fertig! Das perfekte System hat "+input.size()+" Tippreihen!!");
        
        System.out.println("Das perfekte System lautet :");
        System.out.println();
        
        for(ArrayList<Long> stuple: input){
            for(Long a: stuple){
                System.out.print(a+" ");
            }
            System.out.println();
        }
    
    }
    
    
    public static long optimize(ArrayList<ArrayList<Long>> sixtuples,ArrayList<ArrayList<Long>> input){
        
        for(int j=0;j<input.size();j++){
            ArrayList<ArrayList<Long>> copy=copywithoutj(input,j);
            long n=calculate(sixtuples,copy);
            if(n>=3){
                input=copy;
                return 1;
            }
        }
        return 0;
        
    }
    
    public static ArrayList<ArrayList<Long>> copywithoutj (ArrayList<ArrayList<Long>> Array, int j){
        //Sei Array das alte arraylistgebilde
        ArrayList<ArrayList<Long>> copy = new ArrayList<ArrayList<Long>>();

        for (int i=0;i<copy.size();i++) {
            if(i!=j){
                ArrayList<Long> copyi = new ArrayList<Long>();
                for (long Arrayii : Array.get(i)) {
                    Long a=new Long(Arrayii);
                    copyi.add(a);
                }
                copy.add(copyi);
            }
        }
        //copy hat nun die selben inhalte wie array und das ohne referenzen
        return copy;
    }
    
    
    
    
    
    public static ArrayList<ArrayList<ArrayList<Long>>> copy3 (ArrayList<ArrayList<ArrayList<Long>>> Array){
        //Sei Array das alte arraylistgebilde
        ArrayList<ArrayList<ArrayList<Long>>> copy = new ArrayList<ArrayList<ArrayList<Long>>>();

        for (ArrayList<ArrayList<Long>> Arrayi : Array) {
            ArrayList<ArrayList<Long>> copyi = new ArrayList<ArrayList<Long>>();
            
            for (ArrayList<Long> Arrayii : Arrayi) {
                ArrayList<Long> copyii = new ArrayList<Long>();
                
                for (long Arrayiii : Arrayii) {
                    Long a=new Long(Arrayiii);
                    copyii.add(a);
                }
                copyi.add(copyii);
            }
            copy.add(copyi);
        }
        //copy hat nun die selben inhalte wie array und das ohne referenzen
        return copy;
    }
    
    public static ArrayList<ArrayList<Long>> copy2 (ArrayList<ArrayList<Long>> Array){
        //Sei Array das alte arraylistgebilde
        ArrayList<ArrayList<Long>> copy = new ArrayList<ArrayList<Long>>();

        for (ArrayList<Long> Arrayi : Array) {
            ArrayList<Long> copyi = new ArrayList<Long>();
            for (long Arrayii : Arrayi) {
                Long a=new Long(Arrayii);
                copyi.add(a);
            }
            copy.add(copyi);
        }
        //copy hat nun die selben inhalte wie array und das ohne referenzen
        return copy;
    }
    
    public static ArrayList<Long> copy1 (ArrayList<Long> Array){
        //Sei Array das alte arraylistgebilde
        ArrayList<Long> copy = new ArrayList<Long>();
        for (long Arrayi : Array) {
                Long a=new Long(Arrayi);
                copy.add(a);
        }
        //copy hat nun die selben inhalte wie array und das ohne referenzen
        return copy;
    }

    
    
    
    
    
    public static long calculate(ArrayList<ArrayList<Long>> sixtuples, ArrayList<ArrayList<Long>> input){
        //
        
      //anzahl richtige für jedes tupel in input finden   
      ArrayList<Long> wins=new ArrayList<Long>();
      for(ArrayList<Long> sixtuple:sixtuples){
            long wintemp=0;
            //setze wintemp gleich dem maximum, also den größtmöglichen richtigen die mit irgendeiner inputreihe getroffen werden
            for(ArrayList<Long> indinp: input){
                long inttemp=equalnum(sixtuple,indinp);
                if(inttemp>wintemp){
                    wintemp=inttemp;
                }
            }
            wins.add(wintemp);
        }
      
      //bestimmen was die kleinste vorkommende zahl an Richtigen ist
     long minrichtige=getmin(wins);
   return minrichtige;
    }
    
    
    public static long getmin(ArrayList<Long> array){
        long n=array.get(0);;
        for (long zahl:array){
            if(zahl<n){
                n=zahl;
            }
        }
        return n;
    }
    
    
    public static int equalnum(ArrayList<Long> a, ArrayList<Long> b){
        int indexa=0;
        int indexb=0;
        int count=0;
        
        while((indexa<a.size())&(indexb<b.size())){
            if(a.get(indexa)==b.get(indexb)){count++;indexa++;indexb++;}
            if(a.get(indexa)<b.get(indexb)){indexa++;}
            if(a.get(indexa)>b.get(indexb)){indexb++;}
        }
        
        return count;
    }
    
    public static ArrayList<ArrayList<Long>> sixtuples(){
        ArrayList<ArrayList<Long>> sixtuples=new ArrayList<ArrayList<Long>>();
        
        for(long a=1;a<=49;a++){
            for(long b=1;b<=49;b++){
                for(long c=1;c<=49;c++){
                    for(long d=1;d<=49;d++){
                        for(long e=1;e<=49;e++){
                            for(long f=1;f<=49;f++){
                                if((a<b)&(b<c)&(c<d)&(d<e)){
                                    ArrayList<Long> temp=new ArrayList<Long>();
                                    temp.add(a);
                                    temp.add(b);
                                    temp.add(c);
                                    temp.add(d);
                                    temp.add(e);
                                    temp.add(f);
                                    sixtuples.add(temp);
                                }
                            }
                        }
                    }
                }
            }
        }
        return sixtuples;
    }
    
    
    
}
 
G

Gelöschtes Mitglied 65838

Gast
du hast in deiner sixtuples 49^6 Zahlen erzeugt das sind öhm

678.223.072.849 Zahlen die Durchgegangen werden wie viele Tupel erzeugt werden steht in den sternen

und dass eine 6 fach verkettete liste von fors MIT einem if keiner mehr versteht was überhaupt passiert ist glaub ich auch verständlich

da scheitert schon die beuurteilung...du hast angeblich einen Logik fehler drin und es ist normal das man bei 6 fach veketteter for schleifen niemand mehr weis was passiert

und selbst wenn nur das der einzige weg ist ..ein klitzekleines kommentar wäre nett weil die methoden definition nicht mehr ausreicht für sowas:D
 

httpdigest

Top Contributor
Also, beim Lotto 6 aus 49 wird ja jeder 6er Tipp separat für sich gewertet. Wenn du also garantieren willst, dass du bei einem Spiel (Menge aus 6er Tipps) mindestens einen Tipp (ein Spielfeld) dabei hast, welches mindestens 3 Richtige aufweist, dann musst du einfach nur ausrechnen, wie viele Tippfelder du den kaufen musst.
Und das kann man rein mathematisch lösen: Die Lösung ist die Amzahl der Kombinationen mit 3 Elementen einer 49-elementigen Menge. Und das ist der Binomialkieffizient von 49 über 3, was 18.424 ist. So brauchst also 18.424 Spielfelder/Tipps, um zu garantieren, dass mindestens einmal drei richtige vorkommen.
 

berndoa

Top Contributor
Also, beim Lotto 6 aus 49 wird ja jeder 6er Tipp separat für sich gewertet. Wenn du also garantieren willst, dass du bei einem Spiel (Menge aus 6er Tipps) mindestens einen Tipp (ein Spielfeld) dabei hast, welches mindestens 3 Richtige aufweist, dann musst du einfach nur ausrechnen, wie viele Tippfelder du den kaufen musst.
Und das kann man rein mathematisch lösen: Die Lösung ist die Amzahl der Kombinationen mit 3 Elementen einer 49-elementigen Menge. Und das ist der Binomialkieffizient von 49 über 3, was 18.424 ist. So brauchst also 18.424 Spielfelder/Tipps, um zu garantieren, dass mindestens einmal drei richtige vorkommen.
Das geht, wie ich mir so anlas mit wesentlich weniger, nämlich mit 163 Tippreihen (ist so aktuell der Rekord, den es omöglich zu brechen gilt)

Hat einfach damit zu tun dass wenn die Lottozahlen gezogen werden, ja 6 Zahlen gezogen werden.
Rein mathematisch gesprochen lassen sich mit 6 Zahlen ja 20 3-tupel bilden.
Und wenn man nur ein einziges dieser tupel trifft, reicht das shcon um 3 richtige zu haben.

Das verringert daher die menge an nötigen tippreihen so grob schon locker mal auf 1/20 dessen was man bräuchte wenn man alle tripel abdecken wollte.

kluge köpfe haben da in 1950 und danahc wohl dran rumgewerkelt bis sie es auf 163 tippreihen runtergebracht hatten.
Insofern ist der input maximal 163 tippreihen lang zu beginn.

@Joreyk: Der part ist, von meiner programmierersicht her, noch der einfachste part:
egal was beim 6aus49 lotto gezogen wird, das resultierende 6tupel erfüllt ne handvoll von eigenschaften:
1. alle zahlen sind ungleich, es kommt also keine zahl 2mal oder mehr vor.
2. alle vorkommenden zahlen sind aus dem bereich 1-49.
ist ja schließlich wie wenn man aus ner urne mit 49 durchnummerierten kugeln 6 zieht (ist sogar sprichwörtlichgenau das).
3. weils für meine 6tupel vs 6tupel vergleiche praktisch ist, will ich dass alle aufgenommenen 6tupel aufsteigend sind.
hat auch den praktischen nebeneffekt dass ich nicht z.b. zuerst das tupel (1,2,3,4,5,6) und später nochmal das tupel (6,5,3,4,2,1) aufnehme obwohl die tupel ja dieselben sind. ich halte es da im sinne einer mathematishcen menge und streng gneommen nicht wie bei einem tupel.

insofern geht der bereich hier einfach alle 6tupel durch, deren zahlen aus dem bereich 1-49 ist und übernimmt nur jene 6tupel auch in die liste die eben erwähnte eigenschaften erfüllen.

Dass das mit den 6 forschleifen grässlich aussieht und ist, weiß ich.
aber es ist die primitivste erfolgreiche variante.

ich habe ja auch schon über ein zäh int array nachgedacht, aber das würde mir dann zu wäh.
müsste ich überlegen, wenn ich es um 1 erhöhe welche stelle dann auf welche position gesetzt werden kann, darf oder auch nicht.


Ich sage ja, an dem programm ist noch sehr viel sehr hässlich programmiert oder könnte man womöglich viel schöner machen.


gut, die 3 funktionen, die eine deep copy des übergebenen Arraylist Gebildes erzegen, tragen auch nicht zur transparenz bei :)
 

berndoa

Top Contributor
kurze frage: kann ich eigentlich ein ArrayList<ArrayList<Long>> direkt vorgeben, sowas wie {{1,2}{3,4}}?
oder muss ich mich da auch durhc die verschachtelungen durcharbeiten und das long element für loing element einfügen?
 

berndoa

Top Contributor
Ich habe mal betreffend der sache mit den 6er reihen hinzufügen (die sache mit den 6 for schleifen) das ein wenig anders gemacht.
Ob das besser ist oder effizienter als einfach alle 49^6 zahlen durchzugucken und durchzuprüfen weiß ich nicht.

Java:
    public static ArrayList<ArrayList<Long>> sixtuples(){
        int[] array=new int[sixtuples.size()];
        
        //mini={1,2,3,4,5,6}
        int mini=1;
      int[] min=new int[array.length];
        for(int i=0;i<min.length;i++){
            min[i]=mini+i;
        }
        
        
      //maxi={44,45,46,47,48,49}
        int maxi=49;
        int[] max=new int[array.length];
        for(int i=0;i<max.length;i++){
            //maxi-max.length+1=44
            max[i]=maxi-max.length+1+i;
        }
        
        ArrayList<ArrayList<Long>> sixtuples=new ArrayList<ArrayList<Long>> ();
        
        //setze array=mini={1,2,3,4,5,6} zu Beginn
        array=copyarray(mini);
        adding(sixtuples,array);
        
        //erhöhe array um 1 im rahmen der randbedingungen, solange wie möglich, und füge zu sixtuples hinzu
        while(increasing(array)){
            adding(sixtuples,array);
        }
        
        return sixtuples;
            
    }
    
    //fügt eine neue Reihe in sixtuples mit den Zahlen aus array hinzu
    public static void adding(ArrayList<ArrayList<Long>> sixtuples, int[] array){
        ArrayList<Long> line=new ArrayList<Long>();
        for(int a:array){
            line.add(a);
        }
        sixtuples.add(line);
    }
    
    
    //erhöht array um 1, unter beachtung der Randbedingungen
    public static void increasing(int[] array,int[] maxi){
        int index=array.length-1;
        while((array[index]==maxi[index])&(index>=0)){
            index--;
        }
        if(index<0){return false;}
        
        array[index]++;
        
        for (int i=1;index+i<array.length;i++){
            array[index+i]=array[index]+i;
        }
        
        return true;
    }
    
    
    //erzeugt deep copy eines int arrays und gibt sie zurück
    public static int[] copyarray(int[] array){
        int[] copy=new int[array.length];
        for(int i=0;i<array.length;i++){
            copy[i]=array[i];
        }
        return copy;
    }
 

berndoa

Top Contributor
Zur Erklärung wie ich das mit dem array um eins erhöhe mache:

Sagen wir, wir haben das array {1,2,3,4,48,49}
das nächsthöhere im sinne unserer rahmenbedingungen ist dann
{1,2,3,5,6,7}
wie kommen wir da hin?
wir lassen zu beginn den pointer auf das letzte element des arrays zeigen, die 49.
diese ist shcon maximal (weil sie maxi[5] entspricht).
daher gehen wir zur stelle vorher, wo die 48 steht.
diese ist auch maximal (da sie maxi[4]=48 entspricht).
eine stelle nach vorne und wir gucken auf die 4. diese ist NICHT maximal
weil array[3]=4<maxi[3]=47.

wir erhöhen also diese stelle um 1, also nun array[3]=5.

nun machen wir alle dahinter stehenden stellen auf den kleinstmöglichen wert.
daher wird array[3+1] auf 5+1=6 gesetzt.
array[5] wird zu array[3+2]=5+2=7

und so finden wir das "nachfolgerarray".
wenn wir erfolgreich erhöht haben,. geben wir ein true zurück .

woher wissen wir dass das array nicht weiter erhöht werden kann?
weil wir im schritt wo wir gucken ob eine stelle maximal ist und gegebenenfalls eins runter gehen,
bei einem voll maximierten array irgendwann bei index=-1 landen würden.
das würde beim nächsten versuch dann einen arrayoutofbounds error werfen.

darum beachten wir zum einen in der while shcleife dass wir sie nur ausführen solange der index >=0 ist.
und direkt im anschluss prüfen wir ob der index<0 ist. also ob es keine maximierbaren stellen mehr gibt im array.
falls dem so sit, wird false zurück gegeben.

insofern wird in der funktion entweder array um 1 erhöht und true zurückgegeben. oder wir merken dass es nicht erhöhbar ist und geben falls zurück :)
 

berndoa

Top Contributor
gut, die 3 funktionen, die eine deep copy des übergebenen Arraylist Gebildes erzegen, tragen auch nicht zur transparenz bei :)
Wobei mir bei genauerer Überlegung klar wird dass da sehr viel redundanter code drin ist.
bspw. bei einem dreifach vershcachtelten arraylist. bilde ich ja die äussere leere hülle und packe dann arraylist mit einer tiefe weniger sozusagen rein.
diese inneren arraylists liessen sich ja auch mit einer der anderen copy funktionen bauen.
sodass ich nicht das bis ins innerste long element jedes mal komplett bauen muss sondern eifnach auf die schon vorhandenen copy funktionen zugreifen könnte :)

macht zumindest die copy funktionen etwas übersichtlicher und macht auch das prinzip klarer wie man schicht für shcicht obendrauf baut bei dem Ganzen :)

---------------------------

bzgl. meinem vorherigen beitrag fällt mir auch gerade auf dass man realistisch betrachtet die mini und maxi arrays gar nicht braucht, weil ja letztlich der inhalt des jeweiligen arrays direkt vom index der stelle abhängt.

insofern könnte ich unten, wenn ich da irgendwo mini[i9 benutze, auch einfach direkt die entsprechende formel abhängig von i einsetzen und mir die 2 arrays komplett einsparen.

weniger übersichtlich und gut zu verstehen aber von der effizienz und speicherverbrauch her sicher besser :)
 

berndoa

Top Contributor
Ich bin nun an dem punkt wo mein Programm hinreichend gut gemacht ist sodass man es testen könnte.
nur bin ich mir noch unklar wie ich die initialen lottoreihen in das ganze einlesen will...
 

mihe7

Top Contributor
Hat einfach damit zu tun dass wenn die Lottozahlen gezogen werden, ja 6 Zahlen gezogen werden.
Rein mathematisch gesprochen lassen sich mit 6 Zahlen ja 20 3-tupel bilden.
Und wenn man nur ein einziges dieser tupel trifft, reicht das shcon um 3 richtige zu haben.
Kann mir mal jemand erklären, wie man da auf 163 Reihen kommen kann? Das lässt einen ja ganz blöd im Kopf werden.

Wenn es 18.424 unterschiedliche 3-Tupel gibt und ich einen Tipp mit 6 Zahlen abgebe, der 20 3-Tupel enthält, wie bitte kann man dann auf unter 18.424 / 20 = 921,2 Tipps kommen?
 

berndoa

Top Contributor
Kann mir mal jemand erklären, wie man da auf 163 Reihen kommen kann? Das lässt einen ja ganz blöd im Kopf werden.

Wenn es 18.424 unterschiedliche 3-Tupel gibt und ich einen Tipp mit 6 Zahlen abgebe, der 20 3-Tupel enthält, wie bitte kann man dann auf unter 18.424 / 20 = 921,2 Tipps kommen?
Ganz ehrlich?
Keine Ahnung :)

Ich checks auch nicht wie es geht.

Aber ein Gedanke bei dem Ganzen war wohl, wie ich so gelesen habe:
Man überlegt sich Folgendes:
Es werden ja 6 Gewinnzahlen gezogen.
Man unterteilt die zahlen 1-49
in 2 Gruppen A=1-24 und B=25-49 oder so, halbwegs gleich große Gruppen halt.


von den 6 gewinnzahlen sind dann bspw. 2 in A und 4 in B.
oder 1 in A und 5 in B.
oder 3 in A und 3 in B.

was alle diese Aufteilungen gemeinsam haben ist dass in einer der beiden gruppen >=3 Zahlen liegen.


Darum kann man eine Menge an Tippreihen spielen, die mind 3 richtige für die zahlengruppe A garantiert.

und eine weitere Menge an tippreihen mit denen mind. 3 richtige mit zahlen aus B garantiert sind.


hört sich umständlich an, ist es auch.

ich steige da auch nicht 100% durch.

bin jedenfalls mal hingegangen, alle tripel mit zahlen aus 1-24 gebildet und die in lottoreihen zusammengepackt.
gleichermassen habe ich alle tripel mit zahlen aus 25-49 in eine menge an tippreihen gepackt.

beide tippreihen zusammen ergeben das gesamtsystem.

habe noch so meine methoden bzw. algorithmus um die tripel möglichst kompakt in so wenig tippreihen wie möglich zu packen.

So kam ich am ende bei dem ganzen auf 669 bzw. 666 tippreihen.

wie man das runterbricht bis auf 163 tippreihen?
vermutlich durch immer wiedder anwenden eines simplen brute force optimierungs algorithmus.


So wie mein to-be-used programm aktuell auch, welches bei einem system einfach bruteforce mässig immer wieder guckt welche tippreihe man kicken kann sodass trotzdem noch 3 richtige garantiert sind.

hat vermutlich eine abartige laufzeit und speicherbedarf, aber sollte 100% funktionieren :)
 

fhoffmann

Top Contributor
Kann mir mal jemand erklären, wie man da auf 163 Reihen kommen kann?
Jede Lotto-Ziehung enthält ja auch 20 3-Tupel. Also benötigs du mindestens 18.424 / 400 = 46,06 (also 47) Tippreihen.
Da du die Tipprehen jedoch nicht so auswählen kannst, dass du bei bestimmten Ziehungen nicht mehrmals drei Richtige hast, benötigst du natürlich deutlich mehr Tipps. Die Zahl 163 scheint mir nicht absurd zu sein.
 

berndoa

Top Contributor
Kann mir mal jemand erklären, wie man da auf 163 Reihen kommen kann? Das lässt einen ja ganz blöd im Kopf werden.

Wenn es 18.424 unterschiedliche 3-Tupel gibt und ich einen Tipp mit 6 Zahlen abgebe, der 20 3-Tupel enthält, wie bitte kann man dann auf unter 18.424 / 20 = 921,2 Tipps kommen?
wobei du etwas vielleicht falsch verstanden hast:
du tippst nicht ein feld mit 6 zahlen sonder 163(!) felder gleichzeitig!

Nur dann ist garantiert dass du mit einem dieser 163 felder auch 3 richtige haben wirst, egal was letztlich gezogen wird.
 

mihe7

Top Contributor
Jede Lotto-Ziehung enthält ja auch 20 3-Tupel.
An dem Punkt war ich gedanklich schon öfter, leuchtet mir dann erst auch ein und bekomme dann bei weiterem Nachdenken einen Knoten ins Hirn - das treibt mich in den Wahnsinn :)

Ich muss da noch weiter in mich gehen, das lässt mir keine Ruhe.

wie man das runterbricht bis auf 163 tippreihen?
vermutlich durch immer wiedder anwenden eines simplen brute force optimierungs algorithmus.
Mir geht es ja nur um die Anzahl, die müsste doch annähernd ermittelbar sein.
 

berndoa

Top Contributor
Sagt mir Bescheid wenn ihr soweit seid, denn ich würds auch gern verstehen :)
Mit meinem Programm kriege ich es auf 666 Tippreihen runter, aber weiter bisher nicht mehr :)
 

berndoa

Top Contributor
666 - da wundert mich nix mehr.
Jetzt muss ich doch glatt ne Runde Iron Maiden hören :)


ne, war aber kein Scherz.

Am Anfang habe ich einfach alle Tripel aus 1-49 gebaut und in 6Tupel, platzsparend natürlich, gebaut.
Gab um die 4600 Tippreihen, also viel zu viel.

Dann habe ich die Methode mit den 2 Gruppen weiter oben benutzt.
Brahcte es auf 669 Tippreihen.

Dann habe ich mal noch die Art und Weise wie ich Tripel in eine nur wenn nötig wachsende Lsite aus 6Tupeln einfüge, ein wenig optimiert.
Wodurch 3 6Tupel wneiger notwendig waren und wir nun bei 666 Tippreihen sind :)

WIe man von da nun runter auf 163 kommen soll, weiß ich nicht.
Vermutlich schlichte Brute Force Optimierung, ergüäbe irgendwie als Einziges Sinn so :-/

Oder irgendwecleh Mathematiker haben da weitere Tricksereien genutzt, die sie aber nicht unentgeltlich der Welt mitteilen :-(
 

temi

Top Contributor
https://drstefangeorg.de/lotto-spielen-mit-system/ hat gesagt.:
Teilen Sie zunächst die 49 Zahlen in eine Gruppe A von 22 Zahlen und in eine Gruppe B von 27 Zahlen ein, so dass jede Zahl zu genau einer Gruppe gehört. Für die 22 Zahlen aus Gruppe A bietet der Deutsche Lottoblock bereits ein fertiges (VEW-) System an: Die 22 Zahlen sind dabei in insgesamt 77 Tippreihen so kombiniert, dass ein Dreier garantiert wird, sobald 3 der 6 Gewinnzahlen in der Gruppe A enthalten sind. Das ist Weltrekord. Es gibt kein System, das mit weniger Tippreihen auskommt. Entfallen sogar mehr als 3 der 6 Gewinnzahlen auf diese 22 Zahlen, erzielen Sie natürlich höherer Gewinne.

Was aber passiert, wenn höchstens 2 Gewinnzahlen in der Gruppe A der 22 Zahlen enthalten sind? Dann müssen mindestens 4 Gewinnzahlen auf die zweite Gruppe B der 27 Zahlen entfallen. Diese 27 Zahlen sind somit lediglich so anzuordnen, dass bei 4 enthaltenen Gewinnzahlen ein Dreier garantiert ist. Dadurch spart man reichlich Tippreihen ein. Tatsächlich genügen 86 Tippreihen, um 27 Zahlen so anzuordnen, dass bei 4 Treffern ein Dreier garantiert ist. Auch diese 86 Tippreihen gelten (derzeit) als Weltrekord.

Die 77 Tippreihen von Gruppe A und die 86 Tippreihen von Gruppe B ergeben 163 Reihen.
 

berndoa

Top Contributor
Jetzt würde mich ja zum Einen interessieren wie die auf das VEW für A kommen.

Und dann frage ich mich warum bei B 4 Richtige genügen sollen?
es kann doch auch 3-3 zwischen A und B aufgeteilt sein?

Zumal ich nciht den geringsten Plan habe wie man Tippreihen mit Zahlen aus B basteln will unter der Annahme dass B 4 Gewinnzahlen enthält...
 

temi

Top Contributor
https://winnersystem.org/vew622.shtml#auswertung-teilsystem622

Mit zwei und vier Gewinnzahlen ist wohl gemeint, dass zwei der gezogenen Zahlen einer Ziehung unter den ersten 22 waren und die restlichen vier unter den letzten 27. Wären drei der gezogenen Zahlen unter den ersten 22 gewesen, dann hätte man schon den geforderten Dreier gewonnen.

Bei dem zweiten Block handelt es sich also nur noch darum, dass man eine von vier Zahlen richtig haben muss.

Bei dem zweiten Block geht es darum, dass man bei vier gezogenen Zahlen mindestens einen Dreier erhält. Dann ist die Verteilung der sechs Gewinnzahlen auf Block A oder B egal. Wenn drei Zahlen im ersten Block waren hat man automatisch den Dreier. Ansonsten halt im zweiten Block.

Ich hab mir das jetzt aber nicht näher angeschaut, das ist nur meine Interpretation, die noch geprüft werden müsste.
 
Zuletzt bearbeitet:

mihe7

Top Contributor
Mit mathematischen Lösungen kann ich leider nicht dienen. Ich hatte es ja mal erwähnt; Mathe, ganz schlecht...
Ach was, als Mathe-Ass erlange ich auch kein Berühmtheit (sieht dann eher so aus: o_O) Aber es hilft mir schon, Sachen klar zu formulieren, ob das dann formal in jeder Hinsicht korrekt ist, ist mir völlig egal.

So ist das Problem ja leicht beschrieben: wie viele Tippreihen benötige ich mindestens, um bei einer Ziehung von 6 aus 49 mindestens einen Dreier zu erhalten. Formal wird das schon schwieriger, was schon der Präzision geschuldet ist.
 

berndoa

Top Contributor
Ja, mein problem war ja nicht dass ich nicht kapiere was mit "4 Gewinnzahlen aus B" gemeint ist.
Das ist klar.

Ich meinte eher wie man auf die nötigen Tippreihen kommt.

Insofern geht dein Link der Seite wo ich einfahc auf "okay" klicke und kriege die fertigen 77 Tippreihen entgegengeworfen, etwas an meinem ziel vorbei.

Jap, ich will die Mathematik oder Informatik an sich verstehen mit der der Ursprungstyp erstmals auf die 77 Tippreihen kam.
Ich will nicht das Ergebnis haben, sondern den Prozess auf dem Weg dahin verstehen.

Insofern , jo, wirds letztlich um die Mathematik hinter dem Ganzen Spßa gehen.

Ja, beim näheren Überlegen habe ich es jetzt auch soweit kapiert warum 3 zahlen aus A und 4 aus B unser Ansatzpunkt sind.

haben wir die konfiguration 3-3, dann wird da in Dreier garantiert durch die Tippreihen die sich auf 3 Gewinnzahlen aus A stützen.
Die konfiguration 4-2 und 5-1 ist damit natürlich auch abgedeckt.

haben wir hingegen die Konfiguration 2-4, dann erreichen wir die 3 richtige durch die tippreihen die such auf "4 gewinnzahlen aus B" stützen.

1-5 ist natürlich damit auch abgegriffen.

Rein rechnerisch hätte mn es auch spiegelverkehrt machen können,

also tippreihen für "4 zahlen in A" und tippreihen für "3 zahlen aus B" basteln und zusammensetzen.

Was ich (neben vielem Anderen) auch noch nicht kapiere, ist, warum man eigentlich A und B nicht gleich groß macht.
Ich habe in meinem Programm bspw. A und B 24 bzw. 25 zahlen lang gemahct.

Die Typen hier haben stattdessen es in 22 vs 27 zahlen zerlegt.



irgendwie habe ich so ein gefühl, als fehlt mir da ein gewisser grundsätzliches mathematisches konzept.

im prinzip lässt sich ein teilproblem des ganzen (das was B betrifft) beschrieben als
"Wir spielen eine Lotterie wo 4 Zahlen aus dem bereich 1-27 gezogen werden. der spieler darf pro tippfeld 6 zahlen wählen.
wenn mindestens 3 der zahlen übereinstimmen, hat man 3 richtige"

Schweirige gescchichte, eifnahc aus dem grund weil man beim normalen lotto den fall hat wo die anzahl an getippten und die anzahl an gezogenen zahlen beides gleich 6 ist.

und hier ist es stattdessen 6 vs 4.

wir bräuchten hier mal eine mathe stochastik freak der uns aufklärt über den Kram! :-D
 

temi

Top Contributor
Ich habe das mal mit einem kleineren System versucht und zwar "3 aus 6" und gefordert sind Tippreihen, welche mindestens einen Zweier garantieren.

Bei "3 aus 6" gibt es 20 Möglichkeiten, ich habe es derzeit auf 7 Tippreihen gebracht, um diese alle abzudecken.
1
2
3
4
5
6
1
x​
x​
x​
2
x​
x​
x​
3
x​
x​
x​
4
x​
x​
x​
5
x​
x​
x​
6
x​
x​
x​
7
x​
x​
x​
 

fhoffmann

Top Contributor
Das Problem A ist optimal gelöst. Man benötigt midestens
(22 * 21 * 20) / (3 * 2 * 1 * 20) = 77
Tippreihen, um garantiert drei Richtige zu haben.
Die Lösung unter
https://winnersystem.org/vew622.shtml#auswertung-teilsystem622
schafft genau dieses Minimum.
Wie du an den ersten fünf Zeilen siehst, sind alle Kombinationen von 1 und 2 mit allen weiteren Zahlen enthalten und keine Kombination kommt doppelt vor. Das geht nur, wenn die Anzahl der Zahlen (hier 22) von der Form ist 4*n+2.

Wahrscheinlich war die Lösung dieses Problems (A) bereits bekannt. Da war es naheliegend, es bei der Lösung des Gesamtproblems - nach dem Motto "teile und herrsche" - zu benutzen. Übrig bleibt nur noch die Lösung des Problems B.
 

berndoa

Top Contributor
Ich habe mal wieder ne dumme Idee für nen Algorithmus (betreffend der B sache):
naheliegenderweise enthält eine 4er zahl 4 Tripel.
bspw. hat 1,2,3,4 die Tripel
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
nur so als Beispiel.

Als Erstes würde ich mal ne Liste mit allen tupeln aus 4 zahlen basteln.
halt einfahc ne liste aller gewinnzahlen, wenn man so will.
nennen wir das A.

dann nutzen wir ne selbstgebautet methoden, die diese liste aus 4 tupeln umwandelt dergestalt,
dass jenes 4tupel in eine lsite aus 3tupeln umgewandelt wird.

also (1,2,3,4) umgewandelt wird zu
(
(1,2,3),
(1,2,4),
(1,3,4),
(2,3,4)
)

nennen wir diese liste, bestehend aus 3-tupel-listen, A.

nun fangen wir ein leeres array (oder arraylist) B an.
dessen elemente werden 3tupel sein.

wird natürlich anfangs initialisiert und ist zu beginn leer.
wir gehen nun hin und betrachten A[0], also die erste menge an 3tupeln.
wir gucken ob mindestens eines dieser tripel in B enthalten ist.
falls ja, machen wir nix und machen mit A[1].
falls nein, nehmen wir genau eins der Tripel aus A[0] und fügen es zu B hinzu.
(welches tripel man aufnimmt in die liste, lässt sich drüber streiten)

Das mahct man so die ganze liste A durch.

Im prinzip guckt man immer "Ist eins der tripel shcon in der Lsite B enthalten? falls nö, füge eins davon hinzu. ansosnten gehe zur nächsten tripelliste".

nun haben wir also eine Lsite B mit den erfordelrichen tripeln.
Die fügen wir mitz den üblichen methoden in eine möglichst kurze lsite aus 6tupeln ein :)
 

berndoa

Top Contributor
Das Problem A ist optimal gelöst. Man benötigt midestens
(22 * 21 * 20) / (3 * 2 * 1 * 20) = 77
Tippreihen, um garantiert drei Richtige zu haben.
Die Lösung unter
https://winnersystem.org/vew622.shtml#auswertung-teilsystem622
schafft genau dieses Minimum.
Wie du an den ersten fünf Zeilen siehst, sind alle Kombinationen von 1 und 2 mit allen weiteren Zahlen enthalten und keine Kombination kommt doppelt vor. Das geht nur, wenn die Anzahl der Zahlen (hier 22) von der Form ist 4*n+2.

Wahrscheinlich war die Lösung dieses Problems (A) bereits bekannt. Da war es naheliegend, es bei der Lösung des Gesamtproblems - nach dem Motto "teile und herrsche" - zu benutzen. Übrig bleibt nur noch die Lösung des Problems B.
Macht Sinn.

Es gibt definitiv genau (22*21*20)/(3*2*1) Tripel mit zahlen aus 1-22 .
will man die in 6tupel packen, gilt es zu beachten dass in ein 6tupel maximal 20 tripel reinpassen.
Also wenn man alles optimal reinpacken kann, dürften wirklich (22*21*20)/(3*2*1) /20 =77 die perfekte anzahl an 6tupel sein, die sich nicht unterbieten lässt :-/
 

temi

Top Contributor
Es gibt "22 über 3", also (22 * 21 * 20) / (3 * 2 * 1) = 1540, mögliche 3-Tupel in 22 Zahlen.
Mit jedem Tipp erwische ich "6 über 3", also (6 * 5 * 4) / (3 * 2 * 1) = 20, 3-Tupel.
Der Quotient 1540/20 ergibt 77.
Nach der Rechnung stimmt auch die minimale Anzahl von 7 aus #30.

Könnte man sich also nur noch die Frage stellen, ob es eine bessere Aufteilung als 22 / 27 gibt.
 

mihe7

Top Contributor
Mit jedem Tipp erwische ich "6 über 3", also (6 * 5 * 4) / (3 * 2 * 1) = 20, 3-Tupel.
Genau das ist die (m. E. falsche) Überlegung, die mir den Knopf ins Hirn macht. Das funktioniert hier nämlich nur, weil sich die 22 Zahlen disjunkt aufteilen lassen.

Nimmt man zwei konkrete Zahlen, lassen sich mit den verbleibenden 20 Zahlen eben 20 Dreier bilden. Da im Tipp nur zwei Zahlen fest belegt sind, bleiben vier Zahlen im Tipp zur freien Verwendung. Auf diese können die 20 Zahlen nun disjunkt aufgeteilt werden.

Bei 6 aus 49 klappt das nicht mehr: da bleiben 47 Zahlen übrig, so dass bei 12 Tippreihen zwangsweise Duplikate entstehen.
 

fhoffmann

Top Contributor
Ich habe das mal mit einem kleineren System versucht und zwar "3 aus 6" und gefordert sind Tippreihen, welche mindestens einen Zweier garantieren.
Bei "3 aus 6" gibt es 20 Möglichkeiten, ich habe es derzeit auf 7 Tippreihen gebracht, um diese alle abzudecken.
Die Lösung scheint mir falsch zu sein. Du suchst Tippreihen, die alle Kombinationen von Zweiern abdecken (selbst da gibt es eine Möglichkeit mit nur sechs Tippreihen). Um bei jeder Auslosung mindestens einen Zweier zu haben, genügen drei Tippreihen, beispielsweise:
Code:
1 2 3 4 5 6
x x x
x     x x
  x   x   x
Probiere alle 20 möglichen Auslosungen "3 aus 6" aus, und du wirst jedesmal einen Zweier finden.
 

mihe7

Top Contributor
Ich fasse mal zusammen: 6 über 3 = 20 mögliche Ziehungen. Jede Ziehung enthält 6 über 2 = 15 Zweier. Daher braucht man mindestens 1,333..., also 2, Tippreihen. Das "mindestens" ist aber nur als (eine) untere Schranke zu verstehen und bedeutet nicht, dass die Anzahl an Tippreihen einer optimalen Konfiguration tatsächlich nur 2 sind, sondern lediglich dass diese Anzahl keinesfalls unterboten werden kann.
 
Zuletzt bearbeitet:

fhoffmann

Top Contributor
Und ich muss mich korrigieren (oder genauer verbessern): Will man bei "3 aus 6" garantiert zwei Richtige haben, genügen zwei Tippreihen, nämlich:
Code:
1 2 3 4 5 6
x x x
      x x x
Zwei von drei Zahlen liegen entweder in der unteren oder in der oberen Hälfte.

Damit habe ich die "untere Schranke" - Dank an @mihe7 für das Wort - erreicht und das Problem kann nicht weiter verbessert werden.
 

mihe7

Top Contributor
Wieso das? Es werden doch nur 3 Zahlen gezogen. Dann enthält eine Ziehung doch nur 3 Zweier.
Ich sags ja, ich verblöde mit dem Zeug... neuer Versuch aber später, ich hab grad keinen Nerv :)

Nachtrag: Dein Diagramm dürfte dem entsprichen, was ich in #37 meinte. Man kann die Zahlen in diesen Beispielen disjunkt aufteilen, so dass es perfekt passt.
 

berndoa

Top Contributor
Weil ich von der Mathematikseite her gar nicht durchblibke, bleibe ich einfach mal bei meinen Algorithmen. Liefern mir zwar nicht das perfekte Ergebnis, aber doch ein hinreichend gutes wenn ich nur lang genug an dem Ganzen rumschreibe :)
 

berndoa

Top Contributor
Was ich mal grundsätzlich aussagen kann:
ein 6-Tupel enthält (6*5*4)/(3*2*1)=20 Tripel.

Gleichermassen enthält ein 4-Tupel (4*3*2)/(3*2*1)=4 Tripel.

Was man nun mit diesen informationen anfangen kann, weiß ich auch nicht :-D
 

berndoa

Top Contributor
Eines scheint grundsätzlich zu gelten:
Wenn wir wie bei unserem 6 aus 49 3 Richtige wollen.
Und teilen es dann in 2 gruppen A und B ein, wie genau ist für den grundgedanken egal.

dann gibts ja gewisse mögliche konfigurationen:
3-3 bspw.

Diese wird abgedeckt indem man tippreihen hat die "3 zahlen in A" abdecken.

4-2 und 5-1 werden dadurch auch abgedeckt weil 4>3und 5>3.

hingegen gibt es noch 2-4 und 1-5

die lassen sich beide abdecken indem man tippreihen für "4 zahlen in b" findet.

rein rechnerisch könnte man auch tippreihen für "3 zahlen in B" nehmen, dann ginge es auch.

letztlich decken, die tippreihen, die wir für "3 zahlen in A" gefunden haben, alle konfigurationen ab wo der erste wert >=3 ist.
und die tippreihen wo wir "4 zahlen in b" haben, decken (alle verbleibenden) tippreihen ab bei denen die 2. zahl >=4 ist.


ob man für b mit >=4 oder >=3 arbeitet, ist wohl wirklich nur eine frage was einem weniger tippreihen beschert.

genauso wählt man auch, abhängig davon wie viele tippreihen es beschert, wie groß A und B sein sollen.


So langsam kapiere ich wenigstens mal den ersten schritt in dem Ganzen :)
 

temi

Top Contributor
Ich muss hier nochmal nachfragen, weil ich es nicht verstehe. Ausgangspunkt:
Es gibt "22 über 3", also (22 * 21 * 20) / (3 * 2 * 1) = 1540, mögliche 3-Tupel in 22 Zahlen.
Mit jedem Tipp erwische ich "6 über 3", also (6 * 5 * 4) / (3 * 2 * 1) = 20, 3-Tupel.
Der Quotient 1540/20 ergibt 77.
Das wurde als untere Schranke definiert, also mit weniger Tipps geht es nicht.

Dann wurde von mir eine Ziehung "3 aus 6" erfunden, mit dem Ziel mindestens einen Zweier zu haben.
Ich fasse mal zusammen: 6 über 3 = 20 mögliche Ziehungen. Jede Ziehung enthält 6 über 2 = 15 Zweier. Daher braucht man mindestens 1,333..., also 2, Tippreihen. Das "mindestens" ist aber nur als (eine) untere Schranke zu verstehen und bedeutet nicht, dass die Anzahl an Tippreihen einer optimalen Konfiguration tatsächlich nur 2 sind, sondern lediglich dass diese Anzahl keinesfalls unterboten werden kann.
Wieso das? Es werden doch nur 3 Zahlen gezogen. Dann enthält eine Ziehung doch nur 3 Zweier.
In der Rechnung war ein Fehler, der mündlich von @fhoffmann korrigiert wurde. Korrekt wäre also:

Ich fasse mal zusammen: 6 über 3 = 20 mögliche Ziehungen. Jede Ziehung enthält 3 über 2 = 3 Zweier. Daher braucht man mindestens 6,666..., also 7, Tippreihen. Das "mindestens" ist aber nur als (eine) untere Schranke zu verstehen und bedeutet nicht, dass die Anzahl an Tippreihen einer optimalen Konfiguration tatsächlich nur 7 sind, sondern lediglich dass diese Anzahl keinesfalls unterboten werden kann.

Und danach kam dann:
Und ich muss mich korrigieren (oder genauer verbessern): Will man bei "3 aus 6" garantiert zwei Richtige haben, genügen zwei Tippreihen, nämlich:
Code:
1 2 3 4 5 6
x x x
      x x x
Zwei von drei Zahlen liegen entweder in der unteren oder in der oberen Hälfte.

Und jetzt versteh ich es nicht mehr. Was habe ich da falsch gerechnet?
 

berndoa

Top Contributor
Die Rechnung stimmt vermutlich schon, nur kann man diese geringere Reihenzahl, die man mittels Gruppenspaltung hinkriegen kann, mathematisch nicht wirklich erfassen :-/
 

Ähnliche Java Themen

Neue Themen


Oben