Kombinationen

Neue Frage »

badehaubendealer Auf diesen Beitrag antworten »
Kombinationen
Hallo alle,

Folgende Situation: Ich habe einen rekursiven Algorithmus, und möchte wissen, wie viele Rechenschritte der abhängig von den EIngaben braucht. Ich vermute, dass man das Ganze mit etwas Kombinatorik lösen kann, aber das war immer meine Schwachstelle, und jetzt scheitere ich...

Also.

Es gibt eine bestimmte Anzahl an Eingabestrukturen, normalerweise maximal 12. Sagen wir z.B. mal: 2. Die Summe der Populationen aller Strukturen muss stets 1 sein. Ist also z.B. Struktur 1 zu 0,23 besetzt, muss Struktur 2 zu 0,77 besetzt sein.

Der Algorithmus führt jetzt für alle Kombinationen von Populationen irgendeine Rechnung aus, das ist nicht weiter wichtig. Die Frage ist jetzt: Wie viele Kombinationen gibt es abhängig von der Anzahl der reingesteckten Strukturen?

Und weil das ja viel zu leicht wäre, muss noch definiert werden, in welchen Abständen der Algorithmus die Populationen der Strukturen verändert. Diese PopulationStepSize sei ebenfalls ein frei wählbarer Parameter.

Und jetzt will ich also wissen, wie viele Kombinationen es gibt, abhängig von Anzahl der Strukturen und abhängig von der PopulationStepSize.


Ich habe folgendes herausgefunden:
Für 1 Struktur gibt es nur 1 Kombination.

Falls die PopulationStepSize 0,05 beträgt, gibt es für 2 Strukturen 21 mögliche Kombinationen. Für 3 Strukturen gibt es 231, für 4 gibt es 1771, für 5 gibt es 10626, für 6 gibt es 53130, für 7 gibt es 230230 und für 8 gibt es 888030.

Falls die PopulationStepSize 0,01 beträgt, gibt es für 2 Strukturen 101 mögliche Kombinationen und für 3 Strukturen 5151 Kombinationen.

Für 2 Strukturen ist die Sache recht simpel, da kann man das nämlich mit (1 / PopulationStepsize) + 1 ausrechnen.
Für 3 Strukturen kann man die Gaußsche Summenformel verwenden, wenn man den Wert für 2 Strukturen kennt. Also: n sei die Anzahl von Kombinationen für 2 Strukturen. Dann ist die Anzahl an Kombinationen für 3 Strukturen: ( n * (n + 1) ) / 2



So. So weit bin ich gekommen. Die weitere Recherche zu dem Thema hat mich allerdings nur noch mehr verwirrt. Und jetzt stehe ich da und weiß nicht weiter.

Was ich also gerne hätte: Eine Formel, in die ich die Anzahl der Strukturen eintrage, und die PopulationStepSize, und dann kriege ich die Anzahl der Kombinationen raus. Die Herleitung dazu ist mir nicht wichtig, obwohl es mich natürlich interessieren würde.

Ich bedanke mich im Voraus für eure Anregungen und Hilfen smile
René Gruber Auf diesen Beitrag antworten »

Die Frage ist äquivalent dazu:

Wieviele -Tupel nichtnegativer ganzer Zahlen mit Summe gibt es?

Antwort: Kombinationen mit Wiederholung

In deinem Fall ist , also m=20 bei deinen ersten Beispielen



später dann m=100

.
badehaubendealer Auf diesen Beitrag antworten »

Fantastisch. Vielen Dank! Gott
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »