(Twitter)
0
Hallo,
Kombinatorik war nie mein Steckenpferd aber ich würde folgendermaßen vorgehen.
Wir machen 2 Überlegungen. Einmal wie oft kann man die Zahl 11 durch 7 Zahlen aus $\{0,1,\ldots, 10,11 \}$ darstellen (hier ist die Reihenfolge egal). Und dann noch, wie viele Permutationen es pro Fall gibt.
Wir haben
$$ 11 = 11 + 0 + 0 + \ldots $$
und
$$ 11 = 10 + 1 + 0 + \ldots $$
und
$$ 11 = 9 + 1 + 1 + 0 + \ldots $$
und
$$ 11 = 9 + 2 + 0 + 0 \ldots $$
Man erkennt ab hier relativ schnell ein Muster, wie viele Fälle jeweils dazu kommen.
Danach musst du dir also nur noch überlegen, wie viele Permutationen 11 Elemente haben.
Was hälst du davon?
Grüße Christian
Kombinatorik war nie mein Steckenpferd aber ich würde folgendermaßen vorgehen.
Wir machen 2 Überlegungen. Einmal wie oft kann man die Zahl 11 durch 7 Zahlen aus $\{0,1,\ldots, 10,11 \}$ darstellen (hier ist die Reihenfolge egal). Und dann noch, wie viele Permutationen es pro Fall gibt.
Wir haben
$$ 11 = 11 + 0 + 0 + \ldots $$
und
$$ 11 = 10 + 1 + 0 + \ldots $$
und
$$ 11 = 9 + 1 + 1 + 0 + \ldots $$
und
$$ 11 = 9 + 2 + 0 + 0 \ldots $$
Man erkennt ab hier relativ schnell ein Muster, wie viele Fälle jeweils dazu kommen.
Danach musst du dir also nur noch überlegen, wie viele Permutationen 11 Elemente haben.
Was hälst du davon?
Grüße Christian
Diese Antwort melden
Link
geantwortet
christian_strack
Sonstiger Berufsstatus, Punkte: 29.81K
Sonstiger Berufsstatus, Punkte: 29.81K
Ah ich sehe gerade ich habe die Boxen und Schachteln vertauscht. Also suchen wir alle Summen von 7 mit den Zahlen aus $\{0,1,2,3,4,5,6,7 \}$.
Ansonsten würde ich sagen ist unser erster Gedanke ja der selbe.
Das mit den Boxen und Kugeln macht für mich auf jeden Fall Sinn. Allerdings verstehe ich nicht warum $(1,2,3,\ldots , 10,11 ) $ das kleinste Tupel sein soll. Ich würde sagen ab jetzt kann man die Boxen und Kugeln als ununterscheidbar ansehen (weil die Anordnung der Kugeln angibt, wie viele drin sind und weil wir später noch die Permutationen betrachten). Würde es dann nicht eher Sinn machen beispielsweise die Boxen durch $0$ und die Kugeln durch $1$ darzustellen und dann wieder zu prüfen, wie viele Permutationen es gibt, wenn eine Box links bzw. rechts fest ist? ─ christian_strack 23.11.2021 um 13:16
Ansonsten würde ich sagen ist unser erster Gedanke ja der selbe.
Das mit den Boxen und Kugeln macht für mich auf jeden Fall Sinn. Allerdings verstehe ich nicht warum $(1,2,3,\ldots , 10,11 ) $ das kleinste Tupel sein soll. Ich würde sagen ab jetzt kann man die Boxen und Kugeln als ununterscheidbar ansehen (weil die Anordnung der Kugeln angibt, wie viele drin sind und weil wir später noch die Permutationen betrachten). Würde es dann nicht eher Sinn machen beispielsweise die Boxen durch $0$ und die Kugeln durch $1$ darzustellen und dann wieder zu prüfen, wie viele Permutationen es gibt, wenn eine Box links bzw. rechts fest ist? ─ christian_strack 23.11.2021 um 13:16
Hier ist der Link wo das mit den Boxen und Kugeln vorkommt:
https://stackoverflow.com/questions/6508365/list-of-combinations-of-n-balls-in-m-boxes-in-c
Wie gesagt, die ursprünglich zu feinden Tupel sind ja sowas wie (1,11,2,3,11,7) oder so.
Weil es die von mir betrachtete Bedingung herkommt, reicht es wenn ich bei diesem Tupel nur gucke welche Zahl wie oft vorkommt (muss eben am ende berücksichtigen dass ggbfls. andere Anordnungen dieser Zahlen auch zutreffend sind)
Also schreibe ich das als Tupel wo die ite Stelle angibt wie oft die Zahl i vorkommt.
Tupel dieser Art haben eben die Besonderheit dass ihre Zahlen von 0-7 gehen und die Summe alller Elemente 7 ist.
Womti wir beim ball Box Problem sind.
Gegeben 11 Boxen, 7 Kugeln. Und ich verteile die Kugeln irgendwie auf die Boxen, dann kommt ein tupel raus, das eben erwähntem Tupel entspricht.
Oder so. ist einfahc nur sch.. ztu erklären das Ganze.
Jedenflls sind das Boxenproblem und das Tupelproblem mit den elekemtnsumme=7 äquivalent.
wenn die kugel verteilt sind und ich schreibe mir die 11 boxeninhalte als tupel hin, kommt gerade ein tupel mit den gewünschtne eigenschaften raus.
um nunin irgendeiner sinnhaften Art und Weise das mit den boxen durchzugehen, mache ich eben den Trick mit der Aneinanderreihung von kugeln und Boxen.
Und um es programmiertehcnishc einfacher zu machen, frage ich mich nur an welcher der 17 Positionen die 10 Boxen sind (alle anderen stellen sind dann zwangsläufig kugeln.)
Klar könnte man die 16 positionen auch durch 0en und 1en darstellen.
Aber wie geht man da dann systematisch wieder durch sodass genau 11 mal die 1 vorkommt?
Ist ja dann ziemlich gleich dem problem oben wo wir 7 kugeln in 11 boxen verteilen wollten und uns daher zu diesem Umweg entschieden haben.
Ich habe das hier nur so gemacht um das auch programmiert zu bekommen.
letztlich baue ich mir ein 11 tupel, schön aufsteigend sortiert, mit zahlen zwischen 1 und 17.
weil fakt ist, jede box kann nur an einer der 17 positionen sein und keine position kann von 2 boxen belegt werden (was eingangs mit unseren uzahlen nicht so war, da konnte 7 mal die 1 vorkommen)
darum ist es nur eine frage 1 verschiedene zahlen aus der menge 1-17 zu nehmen.
und alle kombinationen hierfür kriege ich durch stupides hochzählen.
Die wortwahl "kleinstes tupel" habe ich nur dher gewählt weil darin eben die kleisntmöglichemn zahlen aus 1-16 vorkommen.
Weil irgendwo muss man ja mal anfangen.
(1,2,3,.....,10) beschreibt eben die anordnung dass von links nahc rechts 10 boxen kommen , dann 7 kugeln und die letzte (programmiertechnisch unsichtbare) box.
rückverwandelt beschreibt das dann das tupel
(0,0,0,0,0,0,0,0,0,0,7)
welches widerum beschreibt dass 0 mal die 1, 0mal die 2, etc. 0 mal die 10 und genau 7 mal die 11 vorkommt.
kurzum, unsere variabeln a-g haben alle den wert 11.
so im prinzip ist es aufgebaut.
Nur da beim programmieren noch den DUrchblick zu behaltne ist hart. Und wird auch nicht besser dadurch dass arrays in java mit index 0 beginnen und daher die indexstellen statt 1-11 dann 0-10 sind und so :-/
Aber programmiertechnisch gehe ich erst alle möglichen boxenpositionetupel durch, werfe jedes dieser tupel in eine "process" methode, die für dieses spezielle tupel das rückumwandelt in das ausgangstupel wo die häufigkeit jeder der zahlen 1-11 damit beshcrieben wird, prüft ob damit die bedingung erfüllt wird.
und falls erfüllt, ist das der methode üergebene tupel gut und daher geht der gesamtcounter hoch.
um genau 7!/(fakultäten der einzelnen werte).
musste mir für den spaß auch eine eignee potenzmethode, fakultätsmethode und array-ausdrucen-methode bauen. weil bspw. math.pow nicht damit klar kommt wenn die basis eine kommazahl ist -.- ─ densch 23.11.2021 um 14:42
https://stackoverflow.com/questions/6508365/list-of-combinations-of-n-balls-in-m-boxes-in-c
Wie gesagt, die ursprünglich zu feinden Tupel sind ja sowas wie (1,11,2,3,11,7) oder so.
Weil es die von mir betrachtete Bedingung herkommt, reicht es wenn ich bei diesem Tupel nur gucke welche Zahl wie oft vorkommt (muss eben am ende berücksichtigen dass ggbfls. andere Anordnungen dieser Zahlen auch zutreffend sind)
Also schreibe ich das als Tupel wo die ite Stelle angibt wie oft die Zahl i vorkommt.
Tupel dieser Art haben eben die Besonderheit dass ihre Zahlen von 0-7 gehen und die Summe alller Elemente 7 ist.
Womti wir beim ball Box Problem sind.
Gegeben 11 Boxen, 7 Kugeln. Und ich verteile die Kugeln irgendwie auf die Boxen, dann kommt ein tupel raus, das eben erwähntem Tupel entspricht.
Oder so. ist einfahc nur sch.. ztu erklären das Ganze.
Jedenflls sind das Boxenproblem und das Tupelproblem mit den elekemtnsumme=7 äquivalent.
wenn die kugel verteilt sind und ich schreibe mir die 11 boxeninhalte als tupel hin, kommt gerade ein tupel mit den gewünschtne eigenschaften raus.
um nunin irgendeiner sinnhaften Art und Weise das mit den boxen durchzugehen, mache ich eben den Trick mit der Aneinanderreihung von kugeln und Boxen.
Und um es programmiertehcnishc einfacher zu machen, frage ich mich nur an welcher der 17 Positionen die 10 Boxen sind (alle anderen stellen sind dann zwangsläufig kugeln.)
Klar könnte man die 16 positionen auch durch 0en und 1en darstellen.
Aber wie geht man da dann systematisch wieder durch sodass genau 11 mal die 1 vorkommt?
Ist ja dann ziemlich gleich dem problem oben wo wir 7 kugeln in 11 boxen verteilen wollten und uns daher zu diesem Umweg entschieden haben.
Ich habe das hier nur so gemacht um das auch programmiert zu bekommen.
letztlich baue ich mir ein 11 tupel, schön aufsteigend sortiert, mit zahlen zwischen 1 und 17.
weil fakt ist, jede box kann nur an einer der 17 positionen sein und keine position kann von 2 boxen belegt werden (was eingangs mit unseren uzahlen nicht so war, da konnte 7 mal die 1 vorkommen)
darum ist es nur eine frage 1 verschiedene zahlen aus der menge 1-17 zu nehmen.
und alle kombinationen hierfür kriege ich durch stupides hochzählen.
Die wortwahl "kleinstes tupel" habe ich nur dher gewählt weil darin eben die kleisntmöglichemn zahlen aus 1-16 vorkommen.
Weil irgendwo muss man ja mal anfangen.
(1,2,3,.....,10) beschreibt eben die anordnung dass von links nahc rechts 10 boxen kommen , dann 7 kugeln und die letzte (programmiertechnisch unsichtbare) box.
rückverwandelt beschreibt das dann das tupel
(0,0,0,0,0,0,0,0,0,0,7)
welches widerum beschreibt dass 0 mal die 1, 0mal die 2, etc. 0 mal die 10 und genau 7 mal die 11 vorkommt.
kurzum, unsere variabeln a-g haben alle den wert 11.
so im prinzip ist es aufgebaut.
Nur da beim programmieren noch den DUrchblick zu behaltne ist hart. Und wird auch nicht besser dadurch dass arrays in java mit index 0 beginnen und daher die indexstellen statt 1-11 dann 0-10 sind und so :-/
Aber programmiertechnisch gehe ich erst alle möglichen boxenpositionetupel durch, werfe jedes dieser tupel in eine "process" methode, die für dieses spezielle tupel das rückumwandelt in das ausgangstupel wo die häufigkeit jeder der zahlen 1-11 damit beshcrieben wird, prüft ob damit die bedingung erfüllt wird.
und falls erfüllt, ist das der methode üergebene tupel gut und daher geht der gesamtcounter hoch.
um genau 7!/(fakultäten der einzelnen werte).
musste mir für den spaß auch eine eignee potenzmethode, fakultätsmethode und array-ausdrucen-methode bauen. weil bspw. math.pow nicht damit klar kommt wenn die basis eine kommazahl ist -.- ─ densch 23.11.2021 um 14:42
Ja das was auf Stackoverflow zu den Boxen und Bällen steht habe ich verstanden und es eine geniale Idee. Die Tupel die danach folgen habe ich missinterpretiert. Ich verstehe jetzt was du meinst.
Ich kann dir leider nicht viel zum programmieren sagen.
Wenn ich dich aber richtig verstehe, geht es dir um die Anzahl aller möglichen Kombinationen und nicht um eine Liste, die alle diese möglichen Tupel erzeugt oder?
Dann ist die Lösung aber viel einfacher.
Wir haben durch den Trick mit den Kugeln und den Boxen insgesamt 17 Positionen die variabel sind (die Box ganz rechts ist ja fest). Wenn wir von 17 unterscheidbaren Objekten die Anzahl aller Permutationen bestimmen, erhalten wir 17! ([Anzahl Kugeln + Anzahl Boxen -1]!)
Nehmen wir mal an, die Kugeln wären beschriftet. Nun macht es denke ich für deinen Fall keinen Unterschied, wenn in der ersten Box die Kugel 1 ist und in der zweiten der Rest oder ob in der ersten die Kugel 2 ist und in der zweiten wieder der Rest. In beiden Fällen ist in der ersten Box eine Kugel und in der zweiten sind 6. Sehe ich das richtig? Falls es einen Unterschied macht, solltest du mit 17! bereits fertig sein.
Wir können uns wieder die Anordnungen der Boxen und Kugeln angucken. Da es egal ist, welche Kugeln in welcher Box sind, müssen wir noch alle möglichen Permutationen der Kugeln berücksichtigen. Das machen wir, indem wir dadurch teilen. Da wir 7 Kugeln haben, können die Kugeln 7! mal vertauscht werden. Also haben wir insgesamt $\frac {17!} {7!} $ Möglichkeiten.
Diese Formel $\frac {n!} {k!}$ findet man auch, wenn man sich Permutationen mit einer Gruppe von Objekten anguckt, die identisch sind (Permutation mit Wiederholung).
─ christian_strack 23.11.2021 um 16:14
Ich kann dir leider nicht viel zum programmieren sagen.
Wenn ich dich aber richtig verstehe, geht es dir um die Anzahl aller möglichen Kombinationen und nicht um eine Liste, die alle diese möglichen Tupel erzeugt oder?
Dann ist die Lösung aber viel einfacher.
Wir haben durch den Trick mit den Kugeln und den Boxen insgesamt 17 Positionen die variabel sind (die Box ganz rechts ist ja fest). Wenn wir von 17 unterscheidbaren Objekten die Anzahl aller Permutationen bestimmen, erhalten wir 17! ([Anzahl Kugeln + Anzahl Boxen -1]!)
Nehmen wir mal an, die Kugeln wären beschriftet. Nun macht es denke ich für deinen Fall keinen Unterschied, wenn in der ersten Box die Kugel 1 ist und in der zweiten der Rest oder ob in der ersten die Kugel 2 ist und in der zweiten wieder der Rest. In beiden Fällen ist in der ersten Box eine Kugel und in der zweiten sind 6. Sehe ich das richtig? Falls es einen Unterschied macht, solltest du mit 17! bereits fertig sein.
Wir können uns wieder die Anordnungen der Boxen und Kugeln angucken. Da es egal ist, welche Kugeln in welcher Box sind, müssen wir noch alle möglichen Permutationen der Kugeln berücksichtigen. Das machen wir, indem wir dadurch teilen. Da wir 7 Kugeln haben, können die Kugeln 7! mal vertauscht werden. Also haben wir insgesamt $\frac {17!} {7!} $ Möglichkeiten.
Diese Formel $\frac {n!} {k!}$ findet man auch, wenn man sich Permutationen mit einer Gruppe von Objekten anguckt, die identisch sind (Permutation mit Wiederholung).
─ christian_strack 23.11.2021 um 16:14
Doch, um die TUpel selbst geht es mir.
Weil ich für jedes Tuel prüfen muss ob es eine bestimmte Bedingung
(Also stark verinfacht geredet, wenn (a,b,c) das Tupel wäre, würde ich prüfen ob bspw. a+2b+0.3c>4. Nur wenn das Tupel auch diese Bedingung erfüllt, sit es relevant und die Zählervariable wird um eins erhöht. Daher sind die Tupel an sich für mich wichtig, nicht nur deren Anzahl. Daher habe ich das Problem ja dass ich jedes einzelne Tupel durchgehen muss und gucken muss ob es die Bedindung erfüllt. Klar könnte ich hier auch mt 7 Schleifen einfahc alle Tupels die möglich sind, durchgucken. Aber ich hoffe zumidnest das smein Algorithmus da effizienter sit au die eine oder andere Art. Vor Allem ist er, insofern ich ihn mal noch so anpasse dass 7 und 11 nicht fest vorgegeben sind, sondern bspw. beim programmaufruf als input eingegeben werden, hoffentlich unabhängiger.
Weil würde ich bspw. ein 15 Tupel, wo die zahlen aus 1-30 sind, machen wollen, müsste ich 15 shcleifen "hard coden" (was den code unflexibel macht) und müsste zudem auch 30^15 Tupel durchgehen, was Leistungstechnisch eventuell schwer wird für den Computer. Sprich ich will es so effizient wie möglich halten damit möglichst nur Tupel betrachtet werden die in Frage kommen. Und so wenig wie nötig geprüft werden muss) ─ densch 23.11.2021 um 20:53
Weil ich für jedes Tuel prüfen muss ob es eine bestimmte Bedingung
(Also stark verinfacht geredet, wenn (a,b,c) das Tupel wäre, würde ich prüfen ob bspw. a+2b+0.3c>4. Nur wenn das Tupel auch diese Bedingung erfüllt, sit es relevant und die Zählervariable wird um eins erhöht. Daher sind die Tupel an sich für mich wichtig, nicht nur deren Anzahl. Daher habe ich das Problem ja dass ich jedes einzelne Tupel durchgehen muss und gucken muss ob es die Bedindung erfüllt. Klar könnte ich hier auch mt 7 Schleifen einfahc alle Tupels die möglich sind, durchgucken. Aber ich hoffe zumidnest das smein Algorithmus da effizienter sit au die eine oder andere Art. Vor Allem ist er, insofern ich ihn mal noch so anpasse dass 7 und 11 nicht fest vorgegeben sind, sondern bspw. beim programmaufruf als input eingegeben werden, hoffentlich unabhängiger.
Weil würde ich bspw. ein 15 Tupel, wo die zahlen aus 1-30 sind, machen wollen, müsste ich 15 shcleifen "hard coden" (was den code unflexibel macht) und müsste zudem auch 30^15 Tupel durchgehen, was Leistungstechnisch eventuell schwer wird für den Computer. Sprich ich will es so effizient wie möglich halten damit möglichst nur Tupel betrachtet werden die in Frage kommen. Und so wenig wie nötig geprüft werden muss) ─ densch 23.11.2021 um 20:53
Puuh ok. Was ist denn die genaue Eigenschaft? Ich weiß nicht ob ich dabei noch helfen kann, denn wie gesagt bin ich nicht sonderlich bewandert was programmieren angeht.
─
christian_strack
24.11.2021 um 11:44
Also programmiertechnisch habe ich was gebaut was, hoffentlich, auch funktioniert.
Würde es an sich auch gerne hier Posten, habe aber keine Ahnung wie am Besten :-/ ─ densch 26.11.2021 um 21:11
Würde es an sich auch gerne hier Posten, habe aber keine Ahnung wie am Besten :-/ ─ densch 26.11.2021 um 21:11
Zur Bedingung:
Sowas wie (1+a)^a*(1+b)^b*(1+c)^c*(1+d)^d*(1+e)^e*(1+f)^f*(1+g)^g>10 oder so.
mein beispiel ist zwar etwas anders, aber hat das selbe prinzip.
Vor Allem die Eigenschaft dass ich links vom > Zeichen die "Reihenfolge" vertauschen kann ohne dass sich das Ergebnis ändert.
Also wenn ich bspw. (a-g)=(1,1,1,1,1,3,1) und (1,3,1,1,1,1,1) habe, dann sind das 2 verschiedene Tupel , müssen daher auch als 2 Tupel betrachtet werden.
Tatasache ist aber dass der Ausdruck auf der linken Seite wegen kommuntatitität und so genau das selbe Ergebnis bringt und daher wird auch von beiden die Bedingung erfüllt.
Kurzum: Habe ich das Tupel(1,1,1,1,1,3,1) betrahctet und herausgefunden , dass dieses die Bedingung erfüllt, dann erfüllen auch alle Vertquchungen (nennt man das Permutationen?) heirvon die Bedingung ohne dass die separat grprüft werden müssen.
Habe icbh also das gültige Tupel (1,1,1,1,1,3,1) gefunden, so habe ich insgesamt 7!/(6!*1!) (weil eben 6 einsen und 1 drei) gültige tupels gefunden.
Mein hübscher counter wird also um den wert erhöht und es geht zum nächsten "unique tupel" (welches also nicht nur eine permutation von was shcon betrahctetem ist).
Damit erspare ich mir (hoffentlich) einiges an computerrechenaufwand wenn ich diese eigenschaft ausnutze :-)
Nur das aufzählen ist ein problem denn:
Praktisch kan ja eine zahl mehrfahc vorkommen (die 1 kommt hier ja gleich 6 mal vor!)
Daher arbeite ich nicht direkt mit den einfachen tupeln, sondern frage mich:
ich habe 7 variabeln, mit den möglichen werten 1-11.
eigentlich reicht es ja zu betrachten, bei einem bestimmten tupel, wie oft die zahl 1, wie oft die 2, etc. vorkommt.
Diese einzelhäufigkeiten zusammen müssen halt wieder 7 ergeben.
Und nun in einem 11 tupel, dessen elemente in summe 7 ergeben müssen, alles durchzuzählen, mahce ich das mit den boxen und kugeln :-)
also 10 boxen (weil eben die 11. box immer ganz rechts ist, die hat keine freiheiten in dem sinne) und 7
kugeln.
Also auf welche arten kann man 10 boxen an 17 möglichen positionen platzieren?
hierzu baue ich mir ein 10 tupel wo jede stelle die position einer box angibt.
jede position sit einzigartig, also kommt in dem zehntupel jede zahl nur einmal vor.
10 zahlen ziehen ohne zurücklegen aus einem zahlenool 1-17. oder so.
DA lassen sich ale kombi simpel durhczählen und hochzählen.
von (1,2,3,4,5,6,7,8,9,10) bis zu (7,8,9,10,11,12,13,14,15,16,17).
so ähnlich läuft der algorithmus.
er geht letztlich alle box-positions-tupel durch, wandelt es dann in das tupel um das angibt wie viel kugeln zwischen linker wand-boxen-rechter wand liegen, wandelt das dann in das "wie oft kommt die zahl 1,2,2,...,10,11 vor, wobei summe=7" tupel um und nutzt die dort gegebenen zahlen direkt in der bedingung oben.
So in der Art läuft das in dem programm bzw. sollte es zumindest :-) ─ densch 26.11.2021 um 21:31
Sowas wie (1+a)^a*(1+b)^b*(1+c)^c*(1+d)^d*(1+e)^e*(1+f)^f*(1+g)^g>10 oder so.
mein beispiel ist zwar etwas anders, aber hat das selbe prinzip.
Vor Allem die Eigenschaft dass ich links vom > Zeichen die "Reihenfolge" vertauschen kann ohne dass sich das Ergebnis ändert.
Also wenn ich bspw. (a-g)=(1,1,1,1,1,3,1) und (1,3,1,1,1,1,1) habe, dann sind das 2 verschiedene Tupel , müssen daher auch als 2 Tupel betrachtet werden.
Tatasache ist aber dass der Ausdruck auf der linken Seite wegen kommuntatitität und so genau das selbe Ergebnis bringt und daher wird auch von beiden die Bedingung erfüllt.
Kurzum: Habe ich das Tupel(1,1,1,1,1,3,1) betrahctet und herausgefunden , dass dieses die Bedingung erfüllt, dann erfüllen auch alle Vertquchungen (nennt man das Permutationen?) heirvon die Bedingung ohne dass die separat grprüft werden müssen.
Habe icbh also das gültige Tupel (1,1,1,1,1,3,1) gefunden, so habe ich insgesamt 7!/(6!*1!) (weil eben 6 einsen und 1 drei) gültige tupels gefunden.
Mein hübscher counter wird also um den wert erhöht und es geht zum nächsten "unique tupel" (welches also nicht nur eine permutation von was shcon betrahctetem ist).
Damit erspare ich mir (hoffentlich) einiges an computerrechenaufwand wenn ich diese eigenschaft ausnutze :-)
Nur das aufzählen ist ein problem denn:
Praktisch kan ja eine zahl mehrfahc vorkommen (die 1 kommt hier ja gleich 6 mal vor!)
Daher arbeite ich nicht direkt mit den einfachen tupeln, sondern frage mich:
ich habe 7 variabeln, mit den möglichen werten 1-11.
eigentlich reicht es ja zu betrachten, bei einem bestimmten tupel, wie oft die zahl 1, wie oft die 2, etc. vorkommt.
Diese einzelhäufigkeiten zusammen müssen halt wieder 7 ergeben.
Und nun in einem 11 tupel, dessen elemente in summe 7 ergeben müssen, alles durchzuzählen, mahce ich das mit den boxen und kugeln :-)
also 10 boxen (weil eben die 11. box immer ganz rechts ist, die hat keine freiheiten in dem sinne) und 7
kugeln.
Also auf welche arten kann man 10 boxen an 17 möglichen positionen platzieren?
hierzu baue ich mir ein 10 tupel wo jede stelle die position einer box angibt.
jede position sit einzigartig, also kommt in dem zehntupel jede zahl nur einmal vor.
10 zahlen ziehen ohne zurücklegen aus einem zahlenool 1-17. oder so.
DA lassen sich ale kombi simpel durhczählen und hochzählen.
von (1,2,3,4,5,6,7,8,9,10) bis zu (7,8,9,10,11,12,13,14,15,16,17).
so ähnlich läuft der algorithmus.
er geht letztlich alle box-positions-tupel durch, wandelt es dann in das tupel um das angibt wie viel kugeln zwischen linker wand-boxen-rechter wand liegen, wandelt das dann in das "wie oft kommt die zahl 1,2,2,...,10,11 vor, wobei summe=7" tupel um und nutzt die dort gegebenen zahlen direkt in der bedingung oben.
So in der Art läuft das in dem programm bzw. sollte es zumindest :-) ─ densch 26.11.2021 um 21:31
Am Ende vom lied gehts mir drum die Frage zu klären, wenn ich eine Geldanlage habe, bei der nahc einem festen zeitraum das Grundkapital plus ein random betrag (der aber innerhalb bestimmer Grenzen ist, also diskrete Werte hat, gleichverteilt, blabla. Sagen wir eine der zahlen 1-11 eben) wieder zurückkommt,
wenn ich da einen geldbetrag nehme und den 7 mal reinstecke (investiere und reinvestiere),
mit welcher Wahrscheinlichkeit wird das, was rauskommt , größer als bspw. das 2 fache des Startkapitals sein?
ich gehe dabei daovn aus dass bei jeder INfestmentrunde der "Randomfaktor" eben random ist und unabhängig bon Vergangenheit und zulkunft.
darum nenne ich die 7 multiplikatoren in den 7 investmentsrunden a,b,c,d,e,f,g.
Im Prinzip könnte ich mir einfahc alle 11^7 tupel bilden, gucken für jedes einzelne ob das resultat größer ist und die anzahl an passenden tupeln durch 11^7 teilen um meine Wahrshcienlichkeit zu kriegen.
Da 11^7 schon goß ist und, wenn ich die anzahl an investmentrunden und den zahlenraum 87 und 1-11 in unserem beispiel) erweitere, habe ich da lächelrich viele Kombinationen und da streikt irgendwann der Computer.
Daurm will ich das intelligent angehen und beim tupelbilden und berechnen so wenig redundanz wie möglich machen.
Einfacher schritt dabei sit eeben die kommutativität auszunutzen :-) ─ densch 26.11.2021 um 21:49
wenn ich da einen geldbetrag nehme und den 7 mal reinstecke (investiere und reinvestiere),
mit welcher Wahrscheinlichkeit wird das, was rauskommt , größer als bspw. das 2 fache des Startkapitals sein?
ich gehe dabei daovn aus dass bei jeder INfestmentrunde der "Randomfaktor" eben random ist und unabhängig bon Vergangenheit und zulkunft.
darum nenne ich die 7 multiplikatoren in den 7 investmentsrunden a,b,c,d,e,f,g.
Im Prinzip könnte ich mir einfahc alle 11^7 tupel bilden, gucken für jedes einzelne ob das resultat größer ist und die anzahl an passenden tupeln durch 11^7 teilen um meine Wahrshcienlichkeit zu kriegen.
Da 11^7 schon goß ist und, wenn ich die anzahl an investmentrunden und den zahlenraum 87 und 1-11 in unserem beispiel) erweitere, habe ich da lächelrich viele Kombinationen und da streikt irgendwann der Computer.
Daurm will ich das intelligent angehen und beim tupelbilden und berechnen so wenig redundanz wie möglich machen.
Einfacher schritt dabei sit eeben die kommutativität auszunutzen :-) ─ densch 26.11.2021 um 21:49
ich ha e mir mittlerweile ein, hoffentlich richtig funktionierendes, java Programm dazu gebastelt.
Weil man vermutlich nciht umhin kommt, alle Fälle durchzugehen.
Wie ich vorgehe:
Ich habe ja 7 Variabeln, die je Werte 1-11 einnehmen.
Alles gleich wahrscheinlich.
Also suche ich alle möglichen 7 Tupel, eins davon ist bspw.
(1,4,2,7,10,5,11)
Weil es in meiner Aufgabe, die ich lösen will so ist dass die Bedingung gewissermassen kommutativ ist,
ist es egal wie genau die 7 zahlen in obigem Tupel angeordnet sind, die bedingung wird entweder erfüllt oder nicht.
(beim betrachten der Fälle muss man hal noch mit einem faktor x die zahl der zutreffenden fälle multiplizieren)
Kurzum, es kommt mir hier nur drauf an dass
je einmal die 1,2,4,5,7,10,11 vorkommen.
Davon ausgehend kann ich genauso gut ein 11 Tupel betrachten wobei die i'te Nummer angibt wie oft die zahl i vorkommt.
Obiges Tupel ist also in der neuen Notation:
(1,1,0,1,1,0,1,0,0,1,1)
Ich muss also alle alle möglichen 11 Tupel durchgehen, bei denen aber die Summe der Elemente 7 ergibt.
Entspricht grob dem Problem wie man 7 Bälle in 11 Fächer werfen kann (wobei hier die Reihenfolge wichtig ist!)
Wie löse ich das wieder?
Dazu habe ich eine recht logische Sache gefunden auf die man erst ma kommen muss:
Ich habe also 11 Boxen und 7 Bälle, die ich darin irgendwie verteilen muss.
Also kann ich hingehen und Bälle und Boxen in eine Reihe stellen dergestalt. dass die Menge an bällen zwischen 2 Boxen in die jeweilgie Box rehts kommt.
natürlich muss die 11. Box ganz rechts sein.
Daher betrachtet man das Problem dergestalt dass man guckt:
wie kann ich 11-1=10 boxen an (11+7)-1=17 positionen verteilen?
Um jede Möglichkeit 11 Boxen an je einer von 17 Positionen hinzusetzen, gehe ich alle möglichen Tupel durch.
Dies tue ich ähnlich wie bei einer 11 stelligen zahl,die ich von der kleinstmöglichen zahl ab immer um 1 erhöhe.
nur mit ein paar Einschränkungen:
das kleisnte Tupel ist ja
(1,2,3,4,5,6,7,8,9,10,11)
das größtmögliche Tupel ist
(6,7,8,9,10,11,12,13,14,15,16)
Anfangs setze ich mein tupel auf das kleisnte tupel.
der um eins erhöhen algorithmus geht dann ähnlich wie beim normalen addieren vor:
er guckt die 11te stelle.
ist sie kleiner als 16 (=11te stelle im max tupel), dann einfahc um 1 erhöhen.
geht das nicht, dann gehe zur 10ten stelle.
falls <15, erhöhen.
falls nicht geht, nächstniedrigere stelle.
Falls der Index hier <1 wird, abbrechen weil die Zahl schon max tupel entspricht und also nicht erhöht werden kann.
falls wir allerdings bei indexstelle c um 1 erjhöht haben, dann gehen hin und erhöhe die rechts davon befindlichen idnexstellen c+i um den wert i.
also die stelle direkt rechts um +1, 2 stellen rechts davon um +2 usw.
so in etwa.
So finde ich also alle 11 tupel im ltztgenannten sinne.
wenn ich nun also alle denkbaren positionen von 11 boxen an 11 möglichen orten habe (in form von passenden 11 Tupeln), dann kann ich diese ja,. unserem gedankengan hier rückwärts gehend, wieder in Tupel umrechnen die mir angeben wie viele kugeln in welcher box landen.
dies entspricht ja gerade der zwischenfrage wie oft jede zahl zwischen 1 und 11 vorkommt.
die häufigikeit jeder der zahlen 1-11 in meinem tupel zu wissen, reicht mir schon aus um die bedingung zu prüfen.
wird die bedingugn erfüllt, haben wir schon 1 güktiges tupel gefunden.
nun ist aber jede permutation(?) daovn auch eine lösung.
beschreibt nun unser tupel zum beispiel die lage dass
5 mal die zahl 3 und 2 mal die zahl 7 vorkommt, so müssen wir der anzahö an gültigen tupeln den ausdruck
7!/(5!*2!) hinzurechnen.
Im urnenmodell könnte mna das als "auf wie viele Arten kann ich 2 blaue und 5 grüne kugeln anordnen?" beschreiben.
insofern würden wir für dieses als gültig befundene tupel der gesamtzahl an gültigen tupeln den ausdruck 7!/(5!*2!) hinzuaddieren.
wenn fertig damit,. dann einfahc die gesamtzahl an gültigen tupels durch 11^7 teilen.
was dann die gewünschte wahrshceinlichkeit gibt :-)
klingt umständlich, ist es auch, hat keinen spaß gemacht zu progrmmieren, sollte aber hoffentlich funktionieren :-) ─ densch 23.11.2021 um 10:47