0

Edit: Um die Frage etwas zu präzisieren:

Wenn die Lsite aus 3Tupeln geordnet ist wie unten, lässt sich bspw. konkret berechnen das wievielte Element der Liste das Tupel (6,33,47) ist?

 

Gibts da mathematisch einen Weg sowas zu berechnen , eben aus den Zahlen 6,33,47?

----------

 

Hallo,

ich bin mir bei der Frage echt nicht sicher ob sie hier her gehört oder doch eher in ein Informatikforum.

 

Mir geht es um Folgendes:

Aus gewissen Gründen betrachte ich aufsteigend sortierte Tupel der Länge 3, deren Elemente aus den natürlichen Zahlen 1-49 stammen (ja, geht  um Lottokram).

Heißt die ELemente der recht langen Liste sind

(1,2,3)

(1,2,4)

(1,2,5)

...

(1,2,49)

(1,3,4)

(1,3,5)

...

(2,3,4)

usw.

bis

(47,48,49)

 

Nun will ich , auf gut Deutsch gesat, die Elemente durchnummerieren.

Also mathematishc gesehen diese Lsite auf die natürlichen Zahlen abbilden oder so.

sodass

(1,2,3) auf 1 abgebildet wird.

(1,2,4) auf 2

(1,2,5) auf 3

....

(47,48,49) auf 18424

 

Gibt es mathematisch oder programmiertechnisch oder irgendwie einen guten Weg, aus einem Listenelement irgendwie direkt seinen "Index" zu bestimmen, berechnen oder so?

 

Ich weiß, die Frage ist recht wage.

Ist keine Hausaufgabe, sondern mhr in logische Problem, dem ich beim Programmieren begegnet bin.

Diese Frage melden
gefragt

Student, Punkte: 286

 

Da man sich nicht selbst antworten kann, hier ein Kommentar:
Ich glaube, ich bin da was auf der Spur:
wollen wir für jetzt das Problem mit den 3tupeln lösen, die von
(1,2,3) bis (47,48,49) gehen.
Betrachten wir das Teilproblem, die 2tupel von (2,3) bis (48,49) durchzugehen.
dies ist ja gleich dem fall wenn wir hingehen, die erste stelle vom 3tupel auf 1 festsetzen und nur die zahlen
(1,2,3) bis (1,48,49) betrachten.

also zum 2tupel problem.
wenn vorne eine 2 ist, dann gehen die zahlen von (2,3) bis (2,49)
Das sind 49-3+1=47 zahlen.
für erste stelle=3 erhalten wir (3,4) bis (3,49).
das sind 49-4+1=46 zahlen.
für erste stelle=4 sind es 45 zahlen usw.
bis erste stelle=48 wo es 1 zahl ist (nämlich (48,49), duh).
kurzum, es gibt also , wenn wir die 2tupel (2,3) bis (48,49) betrachten, entsprechend 47+46+45+44+...+1
=summe i=1 bis 47 von (i)
zahlen.

Nun gucken wir zurück auf das 3tupel und sagen, die 1. stelle sei statt auf 1 auf 2 festgeschraubt. (also (2,3,4) bis (2,48,49)
die hinteren stellen gehen nun also von (3,4) bis (48,49).
Nach gleicher logik wie oben finden wir dass 49-4+1=46
und weiter kriegen wir damit 46+45+44+....+1 zahlen
für den beriech (2,3) bis (48,49).

hm, wir haben also die 1. zahl unseres 3tupels um 1 erhöht (von 1 auf 2) und unsere summe ist von summe i=1 bis 47 von (i) auf
summe i=1 bis 46 von (i) geshcrumpft, sprich, der +47 term ist raus.

auf wähmnliche weise findet man vermutlich der reihe nahc die summen mit obergrenzen 45,44,usw.
bis zum fall, wo wir die 1. stelle des 3 tupels auf 47 festsetzen und damit summe i=1 bis 1 von (i)=1 erhalten.
Was ja sinn mahct, denn es gibt nur (47,48,49).

zählen wir nun alle 47 fälle zusammen (wir haben ja die 1. ziffer des 3tupels auf 47 verschiedene werte festgesetzt gehabt), kommen wir auf (47+...+1)+(46+...+1)+....+(2+1)+(1).

Was in Summenschreibweise offensichtlicher wird was das ist:
Summe j=1 bis 47 von ( Summe i=1 bis j von (i) )


Ohne jetzt die geringste Lust zu haben, das Ganze für 4 5 oder 6Tupel durchzuspielen, würde meine intuition einfach sagen, dass wir für jede stelle mhr einfach eine Summe mehr aussen rum packen ujnd die obergrenze der nächstinneren Summe von der äusseren summenvariaable abhängt.
So wie oben in der inneren summe die obergrenze gleich dem parameter der äusseren summe ist.
schätze, das sich dieses msuter so ewig fortsetzt.

Wäre cool wenn mir jemand sagen könnte ob a) mein gerechne überhaupt stimmt und 2. das Ganze sich wirklich so fortsetzt.


Wobei ich gerade sehe, wenn ich mir das oben ausgeschrieben so angucke, dass da
47*1+46*2+45*3+...+1*47 vorkommt.
Also
=Summe i=1 bis 47 von (i*(48-i)) ist.

Stimmt das Alles so?
Und wie würde der Fall für ein 6 Tupel aussehen? :-)
  ─   densch 23.05.2022 um 00:24

Edit:
Ich habe nochmakl lange nachgedacht und ich hatte das oben vollkommen falsch angegangen.
Nach händschem Durchgehen bin ich auf Folgendes gekommen:
Für die 1Tupel von (1) bis (49) gibt es
(Summe i=1 bis 49 von (1)
Zahlen.

Für die 2Tupel von (1,2) bis (48,49) gibt es
summe j=1 bis 48 von (Summe i=(j+1) bis 49 von (1))
Zahlen

Für die 3Tupel von (1,2,3) bis (47,48,49) gibt es
summe k=1 bis 47 von (summe j=(k+1) bis 48 von (Summe i=(j+1) bis 49 von (1))
Zahlen.

Muster das wir beobachten:
Erhöhen wir die tupellänge um 1, kommt in erster Linie ein Summe... dazu.
Die untere grenze bei der äussersten summe ist immer 1, bei den anderen untergrenzen ist die nächstinnere untergrenze imme aussenvariable+1.

die obergrenzen sind die aufsteigenden zahlen bis 49, so viele halt nötig sind.
konkret gehen die obergrenzen von aussen nach innen
von (49-tupellänge+1) bis 49 (für tupellänge=3 also von (49-3+1)=49-2=47 bis 49, passt also).


Nun stellt sich nur die Frage:
Gibt es einen easy Weg, diese Summen von Summen, wo die Grenzen noch voneinander abhängig sind, irgendwie in einer einfachen expliziten Formel auszudrücken?
Wäre echt praktisch zu haben :-)
  ─   densch 23.05.2022 um 10:22



Dann noch zu meinem ursprünglichen Problem um das es ja eigentlich geht:
gegeben ein 3Tupel (a,b,c)
(der Fall für 4-5 oder 6Tupel nlässt sich darauf bierend sicher auch dann leicht herleiten),
die wievielte zahl in der 3tupel liste ist das?

Dazu betrachten wir mal wie viele zahlen vorher in der Liste gekommen sind.

Betrachten wir wie üblich einfach mal ein Beispiel:

Sei (a,b,c)=(8,24,37)

--------
Zuerst mal alle 3Tupel mit niedrigerer 1. Stelle, also
(1,2,3) bis (7,48,49):

Ohne groß zu überlegen finden wir:
summe k=1 bis 7 von (summe j=(k+1) bis 48 von (Summe i=(j+1) bis 49 von (1))

im Prinzip wie oben, nur steht statt der 47 eben eine 7=8-1 da.
-------

Dann alle ziffern, wo die 1. ziffer gleich 7 ist
und die 2. ziffer <24:

Also Alles von (8,9,10) bis (8,23,49):
summe k=8 bis 8 von (summe j=(k+1) bis 23 von (Summe i=(j+1) bis 49 von (1))

die summe 8 bis 8 habe ich mit absicht hingeschrieben, auch wenn man auch einfach j=8+1=9 einsetzen hätte können.

Wir wollen ja am Ende eine möglichst allgemeine Formel haben :-)
------
nun alle ziffern, wo die 1. ziffer=7, 2. ziffer=24 und 3. ziffer(aka (7,24,25) bis (7,24,36))
summe k=8 bis 8 von (summe j=24 bis 24 von (Summe i=(j+1) bis 36 von (1))
----------
nun alle ziffern wo die 1. ziffer=7, 2. ziffer=24 und 3. ziffer=37, kurzum die zahl (a,b,c):
summe k=8 bis 8 von (summe j=24 bis 24 von (Summe i=37 bis 37 von (1)))
was offensichtlich gleich 1 ist.

Geht nur drum die systematik zu erkennen.

Wir kommen also insgesamt , wenn wir unsere gesuchte zahl mitzählen, auf insgesamt den Ausdruck:
summe k=1 bis 7 von (summe j=(k+1) bis 48 von (Summe i=(j+1) bis 49 von (1))
+summe k=8 bis 8 von (summe j=(k+1) bis 23 von (Summe i=(j+1) bis 49 von (1))
+summe k=8 bis 8 von (summe j=24 bis 24 von (Summe i=(j+1) bis 36 von (1))
+summe k=8 bis 8 von (summe j=24 bis 24 von (Summe i=37 bis 37 von (1)))

Was beobachten wir:
die 1. summe ist gleich unserem allgemeinen Ausdruck von weiter oben, nur dass die äusserste summe von 1 bis a-1 geht.
Die nächste summe hat aussen die grenzen a bis a.
Die nächstinnere summe geht von k+1 bis b-1, weiter innenliegenderes bleibt unverändert.
Bei der nächsten summe sind die 2. äusserten obergrenzen auf a und b festgesetzt, die nächstinnere obergrenze ist auf c-1 festgesetzt. Inneres (wenn es welches gäbe), wäre unverändert.
Und finale summe hat die obergrenzen a,b und c.

Heißt also, die untergrenzen sind wie im allgemeinen ausdruck gleich geblieben: aussen 1, alles innere j=k+1 und so.
Nur die obergrenzen werden der reihe nahc verändert.
Erst wandert a-1 rein.
Dann diese grenze fest auf a, untergrenze auch auf a und die nächstinnere auf b-1.
Dann jene grenze auf b fest, untergrenze auch auf b fest und die nächstinnere auf c-1.
Und final jene grenze auf c und untergrenze auf c, da nichts innereres vorhanden, sind wir fertig

so meine beobachtungen.
Bräuchte ich nur noch eine hübsche formel für den ganzen Spaß :-)

  ─   densch 23.05.2022 um 10:51
Kommentar schreiben
1 Antwort
1

Falls du die Notation "n über m" = $n!\over m!(n-m)!$ (unter dem Namen "Binomialkoeffizienten") schon mal gesehen hast, damit kannst du generell die Anzahlen von (sortierten) Auswahlen von $m$ Elementen aus einer Gesamtheit von $n$ berechnen.

Insgesamt gibt es also bei 3 aus 49 Zahlen 49 über 3, also  $49! \over 46!3!$ = 49*48*47/6 = 18424 Möglichkeiten.

Wie du bereits richtig geschlossen hast, kann man nun also bei einer konkreten  Auswahl, z.B. 3, 14, 42 somit mal etwas schneller zusammenzählen, wieviele vorne eine 1 oder eine 2 haben, dann noch die, die vorne eine 3 gefolgt von einer Zahl im Bereich von 4 bis 13 haben.

Im Endeffekt zählst du dann eine "Handvoll" Binomial-koeffizienten zusammen, und kriegst die Ordnungsnummer.

Diese Antwort melden
geantwortet

Punkte: 265

 

Hm, macht SInn irgendwie.
Betrachten wir mal ein 2Tupel.
für (1,x) bleiben für die 2. stelle noch 49-1=48 zahlen übrig.
Also gibt es 48 über 1 zahlen der form (1,x).

bei (2,x) fallen die 2 zahlen 1 und 2 raus, demnahc sind es 49-2=47 über 1 zahlen.

geht dann hoch bis
(48,x) mit 49-48=1 über 1 zahlen, was natürlich 1 ergibt.
Also:
Summe i=1 bis 48 von (i über 1)

Über den 3tupelfall denke ich dann später nach :-)

Edit:
Wobei ich gerade auf Wikipedia diese Formel gefunden habe:
https://de.wikipedia.org/wiki/Binomialkoeffizient#Summe_verschobener_Binomialkoeffizienten

Vermutlich liesse sich damit die Summe von Binomialkoeffizienten sogar zusammenziehen in einen Binomialkoeffizieten :-)
  ─   densch 23.05.2022 um 11:05

Wenn mich jetzt nicht Alles täuscht, kann man oben erwähnte Wikipedia Formel mit den parametern m=47,n=1 benutzen und erhält damit (nach einem Indexshift um 1 nahc oben) für obigen Ausdruck den Binomialkoeffizient
(47+1+1) über (1+1)=49 über 2
  ─   densch 23.05.2022 um 21:17

1
Falls es geholfen hat, würde ich mich über eine Antwort-Akzeptanz freuen ;-)   ─   mathe42 25.05.2022 um 12:04

1
Klar, gerne doch.
ich bin nur bei der Thematik am Rechnen und habe mir nun fast eine Formel hergeleitet, um den "Index" einer 5-stelligen Zahl zu bestimmen; also wie viele Zahlen zwishcen (1,2,3,4,5) und (a5,a4,a3,a2,a1) liegen, beide eigneschlossen. Darauf basierend kann ih dann natürlich auch den allgemeinen Fall für eine Zahl (an, ...,a1) ablesen.

Werde das noch zu Ende rechnen und dann hier wieder posten.

Aber gerade das mit den Binomialkoffizieten und seinen Rechenregeln hat das immens vereinfacht! :-)
  ─   densch 25.05.2022 um 15:56

Was ich bisher so berechnet habe, wäre gut wenn das Jemand kontrollieren könnte ob es stimmt:
Nachfolgend schreibe ich überall wo ich den Binomialkoeffizient "a über b" meine, dann sowas wie (a,b) .
Nur zur Info dass da keine Vektoren oder sosntwas gemeint sind.

Bei Wikipedia steht ja die Formel
Summe k=0 bis m von (n+k,n)=(n+m+1,n+1)

Nun wollte ich, weil benötigt, mir eine Formel herleiten um für p>q die Summe
(q,q)+(q+1,q)+...+(p,q) zu berechnen.
ich wollte meine wunschsumme so mit obigem ausdruck abgleichen um die formel anzuwenden.
offensichtlich musste schon mal n=q sein, damit es etwas werden konnte.
Doch was müsste das m sein?

daher setzte ich an:
summe k=0 bis m von (n+k,n)
= summe von k=q bis (m+q) von (q+(k-q),q)
=summe k=q bis (m+q) von (k,q)
erneutes vergleichen macht offensichtlich: der binomialkoeffizient hat die passende form, der niedrigste summenterm ist wie erwartet (q,q). nun muss nur noch der oberste summenterm (der dieobergrenze nutzt) gleich p sein.
also: p=m+q->m=p-q

damit kennen wir die für die wikipediaformel benötigten n und m und können also die formel direkt anwenden:
(q,q)+...+(p,q)=(n+m+1,n+1)=(q+(p-q)+1,q+1)=(p+1,q+1)
Also kurzum den größten Ausdruck der Summe (das (p,q)) nehmen und unten und oben +1 machen.

Darauf aufbauend habe ich folgendes betrachtet:
Wir gucken uns einmal 3stellige Zahlen aus einem bestimmten Bereich an:
zuerst die zahlen der form (a,a+1,....)
heißt, es ist gegeben dass die 1. stelle=a ist.
2. stelle ist zwangsläufig a+1(oder größer).
für die letzte Stelle kommen nur zahlen in frage, die größer a+1 sind und kleiner 49.
das heißt, für die letzte stelle sind 49-(a+1) zahlen zur verfügung.
Ergibt also (49-(a+1),1).

für die zahlen der Form (a, a+2, ....) bleiben für die letzte stelle 49-(a+2) zahlen, also (49-(a+2),1) zahlen.
muster dürfte klar sein.
und für (a,b-1,...) ergibt sich dann (49-(b-1),1).

Das heißt weiter, für die zahlen (a,a+1,...) bis (a,b-1,...) gibt es also insgesamt
(49-(a+1),1)+....+(49-(b-1),1) möglichkeiten.

Es sei an dieser Stelle erwähnt dass die zahlen "im zähler" (also die bla zahl im "bla über blu" part)
einfach 49 minus die letzte "festgeschriebene" stelle ist.
und die zahl im "nenner" eben 1 ist weil die zahlen auf genau 1 stellen zu verteilen sind.
dementsprechend ergibt sich für die zahlen (a,a+1, .... , ... , ....) bis (a,b-1, .... , ... , ....) entsprechend bei den binomialkoeffizienten eben ein "... über 3" weils 3 "freie" stellen sind.

weiter im text:
(49-(a+1),1)+....+(49-(b-1),1) ist zu bestimmen. hier machen wir einfach die differenz der summen
(man beachte dass b-1>a+1 sein soll, also 49-(a-1)>49-(b-1) ist)
(49-(a+1),1)+...+(1,1)) - ((49-(b-1),1)+...+(1,1))
mit unserer eingangs bestimmten Formel finden wir dass dies gleich
((49-(a+1)+1,1+1)-(49-(b-1)+1,1+1))
=(49-a,2)-(49-b+2,2)


Nun zu was Handfesterem nach all dem Durcheinander:
Wir wollen wissen, welchen "Index" die zahl 5stellige (a5,a4,a3,a2,a1) hat, also wie viele zahlen vor ihr gekommen
sind +1.
hierzu betrachten wir verschiedene bereiche:
für die zahlen von (1,...) bis (a5-1,...) gibt es
(49-1,4)+...+(49-(a5-1),4)
=(49-1+1,4+1)-(49-(a5-1)+1,4+1)
=(49,5)-((49-a5+2,5)
=(49,5)-((51-a5,5)

für die zahlen von (a5, a5+1, ....) bis (a5, a4-1, ...) gibt es
(49-(a5+1),3)+...+(49-(a4-1),3)
=(49-(a5+1)+1,3+1)-(49-(a4-1)+1,3+1)
=(49-a5,4)-(49-a4+2,4)
=(49-a5,4)-(51-a4,4)

Analog finden wir für die zahlen
(a5,a4,a4+1,....) bis (a5,a4,a3-1,....) dann
=(49-a4,3)-(51-a3,3)

Analog finden wir für die zahlen
(a5,a4,a3,a3+1,....) bis (a5,a4,a3,a2-1,....) dann
=(49-a3,2)-(51-a2,2)

und für den Bereich
(a5,a4,a3,a2,a2+1) bis (a5,a4,a3,a2,a1) finden wir direkt
(a1-a2,1)


Damit ergibt sich , dass sch der Index der 5stelligen Zahl (a5,a4,a3,a2,a1) berehcnenn lässt mittels:
=(49,5)-((51-a5,5) + (49-a5,4)-(51-a4,4) + (49-a4,3)-(51-a3,3) + (49-a3,2)-(51-a2,2) + (a1-a2,1)

Ohne es jetzt mit Induktion bewiesen zu haben 8sowas tue ich mir echt nicht an), vermute ich mit ziemlicher totsicherheit dass eine allgemeine Nummer (an, ... , a1)(also ne aufsteigend sortierte Nummer der Länge n) dann einen Index hat, der sich mit ähnlicher Formel wie oben berechnet:
Vorne ein (49,n)-((51-an,n),
dann für alle i,j mit j=i+1,i>1 Ausdrücke der Form
(49-aj,i)-(51-ai,i)
sowie den festen Schlussterm
(a1-a2,1)
Alles addiert dürfte den Index ergeben :-)

Stellen sich nur 3+ Fragen:
1. Stimmt der ganze Kram überhaupt? :-)
2. Wo ich so meine Zweifel ist, ist bspw. bei einer Zahl wie (3,4, 7,8,10)
Also wo diese Bereiche (a5,a4,a4+1,...) bis (a5,a4,a3-1,....) aus einer (oder keiner?) zahl bestehen, weiö eben a3-1 kleiner oder gleich a4+1 ist. kurzum die fälle wo a4=a3+1 ist, wie siehts da dann aus mit diesen zwischenbereichen, funktioniert da die formel noch? :-/

Weil ich ja durch meine formel vom anfang (die mit p und q drin) aus den summen differenzen gemacht habe, was wenn die ursprungssumme aus einem oder keinem term besteht? funktioniert dann meine umwandlung in ne differenz noch? :-/

3. gibts irgendeinen weg, das ganze irgendwie etwas easier rechnen ohne hunderte summenterme einzeln auszurechnen und zu addieren?
Hätte hier auf sowas wie teleskopsumme gehofft aber egal mit welcher rechenregel für binomialkoeffizienten ich hier ankomme, mir will nichts wirklich kluges in den schoß fallen damit sich was wegkürzt oder irgendwie vereinfacht :-/
  ─   densch 26.05.2022 um 00:10

hinsichtlich meiner Frage 2:
Würde ich von einem KComputerprogramm (java oder so) mir den index berechnen lassen, dann ginge ich vermutlich hin und würde folgendes machen:
Anfangs summe=0 setzen.
dann die ausdrücke (49,n)-((51-an,n) und (a1-a2,1)

und danach für jedes paar (i,j) mit (j=i+1) und (i>1) gucken:
falls ai>aj+1 ist (also kurzum bei der zahl (..., aj, ai, ....) das ai nicht die nahcfolgerzahl von aj ist), dann zu summe den Ausdruck
(49-aj,i)-(51-ai,i) hinzuaddieren.
falls hingegen ai<=aj+1, den summenausdruck ignorieren und zum nächsten gehen.


Kurzum, ich würde für jedes i,j das mit fallunterscheidungen prüfen und dementsprechend handeln.
Aber mathematisch lässt sich das nicht irgendwie bewerkstelligen, im sinne einer expliziten formel?
  ─   densch 26.05.2022 um 00:19

Ich habe etwas weiter rumgerechnet:
Erst mal eine allgemeine herleitung eienr Rechenregel u(hoffe ich zumindest dass es richtig ist):
seien a,b nat. zahlen mit a>b. dann sollte eigentlich sein:
(a,b)
= a!/(b!*(a-b)!)
kann man aus a! ein a rausziehen und aus (a-b)! den (a-b) term:
=a/(a-b) *((a-1)!/(b!(a-b-1)!)
=a/(a-b) *((a-1)!/(b!((a-1)-b)!)
=a/(a-b) *(a-1,b)
kurzum, (a,b) ist ein bruch mal (a-1,b) wo also nur der "zähler" verkleinert wird.

Damit müsste dann weiter bspw. gelten:
->(51-a5,5)
=((51-a5)/5) * (50-a5,4)
=((51-a5)/5) * (50-a5)/(50-a5-4) * (49-a5,4)
(hier habe ich auch die wikipedia regel benutzt dass
(n,k)=(n/k)*(n-1,k-1) ist

damit folgt dann weiter:
Also
+ (49-a5,4)-(51-a4,4)
=(49-a5,4)-(((51-a5)/5) * (50-a5)/(50-a5-4) * (49-a5,4))
=(49-a5,4)* (1 - (51-a5)/5) * (50-a5)/(50-a5-4)
kurzum, Alles wo das a5 drin vorkommt lässt sich als ein binomialkoeffiziente mal einer (hässlichen) zahl/bruch schreiben.

das kann man sich für den fall mit j=i+1 usw verallgemeinern, obs jetzt groß was hilft beim ganzen, weiß ich nicht :-/
  ─   densch 26.05.2022 um 01:34

1
Vielleicht lässt sich das mit kleineren Zahlen etwas leichter testen, zum Beispiel von 1 bis 10 (gibt dann nur 120 Möglichkeiten). Programmiertechnisch ist das ja relativ leicht umzusetzen. Was ist eigentlich das Ziel des Ganzen?   ─   cauchy 26.05.2022 um 01:38

Öh, der Hintergrund ist ein programmiertechnischer.

Es geht darum:
Es gibt ja das Lotto 6aus49 und es gibt so Lsiten an Tippfeldern (also an 6Tupeln).
wenn man die alle auf einmal tippt, ist sichergestellt dass man 3 Richtige hat.
Weil die so gewählt sind dass bei der Ziehung irgendeine dieser Zahlen in der Liste 3 Zahölen gemeinsam hat mit der Gewinnkombi, egal welche 6 Zahlen bei der Sitzung gezogen werden.

Nun kann man mit mathematischen Tricks sich eine halbwegs kurze (heißt, nur ein parr Tausende Einträge) Lsite basteln, die die "3Gewinnt Garantie" erfüllt.

Was aber nicht heißt, dass diese Lsite schon zwingend "optimal" ist.

Es könnte schließlich sein dass da Zahlenkombis drin vorkommen, ohne die die Liste auch immer funktionieren würde.

Daher will ich programmiertechnisch in Runden arbeiten und in jeder Runde versuche, eine Zahlenkombi in der Lsite ausfindig zu machen, die überflüssig ist, und die rauszuwerfen.

Um das zu bewerkstelligen, habe ich 3 Listen (alle nur mit aufsteigend sortierten Zahlenkombis):
Liste A, die einfach alle möglichen Lottozahlen aka alle 6Tupel enthält ((1,2,3,4,5,6) bis (44,45,46,47,48,49)).
Liste B, die alle möglichen 3Tupel enthält (also (1,2,3) bis (47,48,49)).
Und die Liste C, die ist unsere vorgegebene, suboptimale "3Gewinnt Lsite", die wieder rekursiv immer weiter verkleinern wollen.

In einem ersten Schritt will ich von den Zahlenkombos wie (1,4,6,8,33,45) oder (12,20,27) auf entsprechende positionen in der Lsite abstrahieren.
Auf gut Deutsch gesagt, durchzählen.
Schließlich kann man ja auf die offensichtlichste Art alle Zahlenkombis in der betreffenden Lite durchgehen und dementsprechend auch jeder Kombi einen Index geben.

Dann kann ich später, statt auf "(1,4,6,8,33,45) aus Liste A", einfahc nur sagen "Element Nr. 1765 au Liste A".

Hat später Vorteile.

Denn beim Optimieren will ich folgendes machen:
Man stelle sich mal in guter alter Mathemanier so die hübschen Bilder vor, die man bei surjektiv, injektiv, bijektiv malt.
so stünden links die elemente der Lsite A untereinander, mittig die Elemente der Liste B und rechts die der Liste C.

Und es gäbe verbindungen (striche) zwischen mancher der linken und der mittigen, sowie der mittigen und der rechten Elemente.

Linkes element wird mit 6*5*4/3*2*1=(6 über 3)=20 mittigen elementen verbunden.
nämlich wird das linke 6tupel genau mit den 20 mittigen 3tupeln verbunden, aus denen es besteht.

und das halt für JEDES linke element.

und dann das selbe spiel von rechts zur mitte.

dann gehen also von jedem element links und rechts jeweils 20 verbindungen zu elementen in der mitte.

jetzt zu meinem hintergedanken bzgl. dem 3gewinnt:

betrachten wir mal eine beliebige zahl links.
von dieser gehen 20 verbindungen zu 20 mittigen elementen.
von jedem dieser mittigen elemente gehen unzählige verbindungen zu elementen rechts.
was bedeutet nun so ein pfad von links über mitte nahc rechts?
jenes linke element enthält unter Anderem jenes mittige element, welches wiederum auch im nahc rechts verbundenen element vorhanden ist.
linkes und rechtes element teilen sich also das mittige 3tupel.

nun will ich hingehen und zähler einführen:
jedes mittige element "merkt sich" wie viele verbindungen nach rechts abgehen.
Das ist ja dann gerade die anzahl an 6tupeln, rechts, die die zahl enthalten.
und das für jedes mittige element, jedes hat einen simplen int zähler.

und jedes linke element kriegt einen zähler, der ist nämlich gerade die summe der zähler in der mitte.

Mathematisch gibt ein zähler bei einer linken zahl an mit wie vielen rechten zahlen er verbunden ist, wie viele pfade von der linken zahl aus nach rechts es gibt.
aka wie viele zhalen rechts mind 3 gleiche mit der linken zahl haben
(klar, wird manches doppelt gezählt, stört aber nicht).

So wird das anfangs initialisiert , die mittigen und linken elementen kriegen ihren zähler gesetzt.

Nund zum optimieren:
Wir wollen ja wissen ob eine zahl überflüssig ist.
dazu können wir nun ganz simpel hingehen und versuchen mal das 1. element aus der rechten liste zu entfernen,
hierzu wird bei allen mittigen elementen , die dmait verbunden sind, der zähler um 1 reduziert. weil dann halt eine verbindung nahc rechts wegfällt.
gleichzeitig, da sich gerade um die 20 mittigen zähler um 1 rediuziert haben, müssen sich dann mit jenen mittenelementen verbundene linke zähler auch entsprechend verringern.
ist die linke zahl mit n der betroffenen mittenelementen verbunden, dann geht der zähler des linke elements um n runter.

nun wird es interessant ob nach "updaten" aller zähler nun links elemente vorkommen, deren zähler=0 ist.
denn dies hieße, es besteht für jene zahl keine verbindung nach rechts mehr
heißt im umkehrschluss, es gibt also mögliche lottoziehungen, für es keine rechte listenelemente gibt, die 3 richtige bringen.

istn also nach dem entfernen des rechten elements auch nur ein zähler =0, dann war das rechte element sehr wichtig und muss wieder hinzugefügt werden.
haben wir also gefunden dass bspw. das 1. rechte element essentiell war, machen wir mit dem 2. weiter und testen ob das gelöscht werden kann.

dann das 3. usw.
wir hören mit der aktuellen runde auf, sobald ein löschbares element gefunden und, naja, halt gelöscht wurde.
dann gehts mit der nächsten optimierungsrunde wieder los.

Oder wir haben das listenende erreicht und konnten nix löschen, dann ist die lsite schon optimal.

Nun kann es sein dass je in einer runde mehrere rechte elemente löschbar wären und jenach "löschreihenfolge/-pfad" wir am ende vielleicht eine kürzere oder längere optimale lsite erhalten.

Daher merken wir uns auch stets mal, wie wir ausgehend von der Startliste in welcher reihenfolge was gelsöcht haben.
Damit wir später vielleicht noch einen anderen "löschpfad" testen können.

Zurück kurz zum Algorithmus:
Um beim löschen des rechten elements bei den verbundenen mittigen elementen den zähler runterzusetzen, mssen diese verbindungen natürlich bekannt sein.
insofern muss sich jede rechte zahl irgendwie speichern mit welchen mittigen elementen sie verbunden ist.
Gleichermassen müssen auch die mittigen elemente wissen mit welchen linken zahlen sie verbunden sind.


Ansosnten, mehr um etwas zeit zu sparen, würde ich noch eine minimumzal einführen die eben das Minimum aller linken elemente ist.

dann kann man, wenn man gewisse linke zähler verändert, gucken "ist der verändette zähler nun < als das minimum? falls ja, ist es das neue minimum.
nach dem abändern aller linken zähler muss man dann nur auf das minimum gucken und abgleichn ob es nun 0 oder kleiner ist.
hat halt den vorteil dass man nicht nochmal alle paar millionen linken zähler durchgucken muss um nach 0-zählerständen ausschau zu halten, weil uns die minimum variable schon die Antwort gibt.


So ine twa das Prinzip.

Die MAtherechnerei hier dient sprichwörtlich nur dazu, aus einem Sechstupel eine einzige zahl, den index zu machen.
Falls ich, was ich wohl werde, arrays benutzen werde, dann
brauche ich bspw. nicht nach der zahlenkombi (30,44,46) in der mitte zu suchen (wozu ich JEDES element der mittigen liste damit vergleichen kann, also 3tupel mit 3tupel vergleichen müsste. und das für 49 über 3 elemente, nur um ein bestimmtes lsitenelement überhaupt zu finden!),
sondern kann direkt sagen :
mittenarray[indexdesElements]--;
so als java code, wobei ich halt noch beachten muss dass java array indizes bei 0 und nicht bei 1 beginnen.

Kann also einfahc auf das xte element der lsite verweisen, ohne erst vergleiche mit allen vorherigen x-1 elementen langwierig machen zu müssen.

Daher diese umständliche formelsuche.

eine Art "Übersretzungstabelle" von 3 oder 6Tupel in zugehörige Indexnummer lässt sich ja ggbfls
schon vorab ausrechnen und abspeichern, kann man also aus den optimierungsrunden auslagern.

  ─   densch 26.05.2022 um 03:21

Über was ich so im Hinterkopf auch noch nahcdenke:
Irgendwie muss ich ja auch wissen, welche 3Tupel aus der Mitte auf 6Tupel links verweisen.

Wenn ich also bspw. das 3Tupel (2,6,9) habe,
dann würde ich mir gerne alle 6Tupel finden, die dieses 3Tupel enthalten. (wenn ich die habe, kann ich die natürlich mit altbekannter formel wieder in indizes umrechnen)
wobei ich da halt dieses Mal dann alle konkreten 6Tupel suche, die die 2,6 und 9 enthalten, sowie 3 andere Zahlen aus 1-49, und die 3 mysteryzahlen halt passend paltziert sein können vor zwischen und hinter den 3 belannte nummern.
das zu bestimmen wird dnan nochmal sehr nervig :-/
  ─   densch 26.05.2022 um 03:25

1
Das ist jetzt viel Lesestoff... vielleicht komm ich morgen dazu... ;-)   ─   mathe42 26.05.2022 um 08:36

Kommentar schreiben