Alle Zahlen finden, die 3 bestimmte Ziffern enthalten?

[berndoa]

Hallo,
ich werkle mal wieder an meinem Lottoproblem und der bisherige Code ist insofern aktuell performancemässig... miserabel
da der Code ein aufsteigend sortiertes Tripel (a,b,c) (mit a<b<c, 1<=a,b,c<=49) aktuell mit 13 Millionen 6-Tupeln (g,h,i,j,k,l) dahingehend vergleicht ob es darin enthalten ist. (zuzüglich 1-2 weiteren Bedingungen).
Falls dem so ist, dann geht der Code nochmal alle 6-Tupel durch und entfernt darin dieses Tripel.
Und das wieerum wird für ALLE möglichen Tripel gemacht.


Kurzum, es werden so ca. 2*(49 über 3)*(49 über 6)=515275651968 Vergleiche gemacht, was einfahc nur lächerlich hoch ist, was seeehr lange dauert und den Computer zum Abshcmieren bringt.

Um also zumindest ein 3-Tupel nicht 2 mal mit 13 Millionen 6-Tupeln vergleichen zu müssen,
war nun der Gedanke, sich vorab einfach mal zu überlegen, welche 6tupel es denn gibt in denen ein gegebenes 3-Tupel (a,b,c) enthalten sein könnte.
Und nur die dann überprüfen!

Das erscheint mir, als wäre es unter Umständen etwas schneller und effektiver! 🙂

Frage ist nur, wie alle möglichen solchen 6Tupel bauen?
Wenn ein 3Tupel (a,b,c) gegeben ist, kann ja das 6Tupel bspw die Formen
(___abc),(a_b_c)(a__bc) und ähnliche haben.
Wie finde ich die am Effektivsten?

Wobei halt die 3 Blnkstellen _ _ _ in und um a b und c verteilt werden müssen.


Ist vermutlich eher eine Frage der Kombinatorik, aber mir fällt nichts Gutes ein wie ich das programmieren kann :-/

 

[berndoa]

Ich habe glaube ich, vemrutlich, eine halbwegs wirksame Idee:
Anfangs Array(list?) mit Zahlen 1-49 bauen.
Dann die 3 Zahlen, a,b,c rausschmeissen.
Dann systematisch alle aufsteigend sortierten Tripel aus diesem Array ziehen, wobei all jene Tripel jeweils mit dem Ursprungstripel (a,b,c) zu neuen 6-Tupel fusioniere.

Müsste dann entsprechend alle 6Tupel ergeben wo das besagte (a,b,c) Tripel drin ist.

 

[Neumi5694]

Effizienter. Entweder kommt bei deinem Code effektiv das richtige raus oder eben nicht 🙂

Falls du mit einem Filter arbeiten willst, ist einer mittels Bitmaske recht effizient.

long tupel6; //hat 6 Bits auf 1
long mask; //hat 3 Bits auf 1
if  (tupel6 & mask == 0) {
  //Keine Übereinstimmung
}

Aber wenn du von Anfang an nur Tupel bilden willst, die diese Zahlen nicht beinhalten, dann ist natürlich eine Reduzierung der Datenmenge besser, da du dann nur mit 46 über 6 arbeitest anstatt mit 49 über 6, der Faktor müsste bei ca. 18000 liegen.
Nachteil: Für jede Dreierkombi musst du zuerst mal diese Liste aufbauen, was wiederum Leistung kostet.Ich weiß auch nicht, wie oft du das machen willst. Wenn es für jede Dreierkombination einmal passieren muss, dann hast du am Ende einen höheren Aufwand als wenn du einmal alle möglichen Tupel erstellst und dann für jede Dreierkombination filterst.

 

[Neumi5694]

ps: Im Threadtitel steht, dass du Zahlen finden willst, die diese 3 beinhalten, im Text willst du diese ausschließen.
Zum finden der Tupel MIT Diesen Zahlen wäre der FIlter dieser:

if  (tupel6 & mask == mask) {
  //Alle Bits der Maske sind in tupel6 gesetzt.
}

 

[mihe7]

Läuft in unter einem Wimpernschlag:

public long[] dreier(int a, int b, int c) {
     long[] ziehungen = new long[15180];
     long ziehung = 1L << (a - 1) | 1L << (b - 1) | 1L << (c-1);
     int count = 0;
     for (int d = 1; d <= 47; d++) {
         if ((ziehung & (1L << (d - 1))) > 0) continue;

         for (int e = d + 1; e <= 48; e++) {
             if ((ziehung & (1L << (e - 1))) > 0) continue;

             for (int f = e + 1; f <= 49; f++) {
                 if ((ziehung & (1L << (f - 1))) > 0) continue;

                 ziehungen[count] = ziehung | 1L << (d - 1) | 1L << (e - 1) | 1L << (f - 1);
                 count++;
             }
         }
    }
    return ziehungen;
}

 

[berndoa]

ps: Im Threadtitel steht, dass du Zahlen finden willst, die diese 3 beinhalten, im Text willst du diese ausschließen.
Zum finden der Tupel MIT Diesen Zahlen wäre der FIlter dieser:

if  (tupel6 & mask == mask) {
  //Alle Bits der Maske sind in tupel6 gesetzt.
}

Was ich meinte:
Ich habe gegebenes Tripel, bspw. (1,4,5)

Dann nehme ich die reduzierte Liste an möglichen zahlen , also {1-49}/{1,4,5}={2,3,6,7,...,49}.
bilde alle möglichen Tripel mit dieser menge und vereinige jene Tripel jeweils mit dem ursprungstripel.

Weil, ich meine, ein 6tupel, das 1,4,5 enthält, besteht ja zwangsläufig
aus 1,4,5 sowie 3 weiteren, bisher noch nicht benutzten zahlen.
also halt (1,4,5) und ein solches tripel mergen wobei ich ausnutze dass beide tripel aufsteigend sortiert sind und so auch ein aufsteigend sortiertes 6tupel baue.

Gedenke nicht die ganzen 6tupel zu speichern, sondern nur mit dem 6tupel->string->id zu gehen und mit dem speziellen 6tupel zu arbeiten.

Ist vielleicht etwas besser wie wenn ich jedes tripel jeweils mit jedem der 13 millionen 6tupel abgleiche.


Ist zwar im Prinzip nur Schadensbegrenzung aber naja, vielelciht besser als Ohne 🙂

Stellt sich nur die Frage ob man bei eienr Hashmap sinnvoll Strings als keys benutzen kann.
Und ob er den key in der Hashmap auch dann findet wenn ich einen neuen string mit gleichem inhalt wie der key string benutze (weil ja inhalt gleich aber objekt hashcode unterschiedlich. vermutlich).

 

[Neumi5694]

... Wozu so umständlich?
Du hast eine feste Menge an möglichen Sechsertupeln (49 über 6). Die hast du einmal erstellt und kannst sie immer wiederverwenden.
Lass den Bitmaskenfilter (D & m == m) darüber laufen und du kriegst genau das raus, was du gesucht hast, das geht sehr schnell.
Du weißt sogar, wie viele Zahlen du für den Filter rauskriegst (46 über 3) und kannst schon mal entsprechend dein Ergebnisfeld initialisieren.

 

[mihe7]

Was gefällt Euch an #5 nicht?

 

[Neumi5694]

Klappt natürlich auch. Lass mal beides laufen, schauen, was schneller ist 🙂

 

[berndoa]

Ich werde dann mal gucken ob ich was Eigenes mit den Sachen zusammenkriege