Anzahl Möglichkeiten berechnen

[gkieninger]

Hallo!

Ich bräuchte eine Hilfe um die Anzahl der verschiedenen Möglichkeiten zu ermitteln. Bin leider in Mathe nicht wirklich gut unterwegs.

Gegeben sind zum Beispiel 3 Nächte (1.5 bis 4.5). Nun müsste ich wissen, wieviel Übernachtungsmöglichkeiten es gibt
Also in dem Beispiel wären das 6 Möglichkeiten
1 -> 1 Nacht von Tag 1 weg
2 -> 2 Nächte von Tag 1 weg
3 -> 3 Nächte von Tag1 weg
4 -> 2 Nächte von Tag 2 weg
5 -> 1 Nacht von Tag 2 weg
6 -> 1 Nacht von Tag 3 weg
(Hoffentlich nichts vergessen )

Gibt es da eine einfache Möglichkeit um das flott zu berechnen?
Vielen Dank für jeden Hinweis!

[rogerb]

@gkieninger,

ich komme auch auf 6 Übernachtungen:

Mögliche Übernachtungen (von - bis):
1.5. bis 2.5.
1.5. bis 3.5.
1.5. bis 4.5.
2.5. bis 3.5.
2.5. bis 4.5.
3.5. bis 4.5.

Eine Übernachtungsmöglichkeit ist ein Zahlenpaar aus Anreisetag und Abreisetag.
Alle möglichen Kombinationen der Tage 1, 2, 3, und 4 sind eine Übernachtung, mit der Einschränkung, dass die zweite Zahl größer sein muss als die erste.

Es gibt in Python eingebaute Werkzeuge, die einem enorm dabei helfen, diese Kombinationen aufzustellen.
Wenn man es zür Übung von Hand programmieren will, sind das zwei verschachtelte Schleifen die jeweils über Ankunftstage und Abreisetage iterieren.

[nezzcarth]

Unterbrechungen zählen also nicht? Ansonsten gibt es noch die Variante mit je einer Übernachtungen 1. und am 3.

[pillmuncher]

Von einem Tag zum nächsten ist es 1 Nacht: 1*1
Von einem Tag zum übernächsten sind es 2 Nächte: 1*2 + 2*1
Von einem Tag zum überübernächsten sind es 3 Nächte: 1*3 + 2*2 + 3*1
Von einem Tag zum überüberübernächsten sind es 4 Nächte: 1*4 + 2*3 + 3*2 + 4*1
...

Den jeweils zweiten Faktor kann man weglassen, weil er nicht als Zahl in das Ergebnis einfließt:

Von einem Tag zum nächsten ist es 1 Nacht: 1 == 1
Von einem Tag zum übernächsten sind es 2 Nächte: 1 + 2 == 3
Von einem Tag zum überübernächsten sind es 3 Nächte: 1 + 2 + 3 == 6
Von einem Tag zum überüberübernächsten sind es 4 Nächte: 1 + 2 + 3 + 4 == 10
...

Ganz offensichtlich haben wir es hier mit der Summe der natürlichen Zahlen von 1 bis n zu tun. Und dafür ist die Formel n(n+1)/2. Also bei insgesamt 5 Nächten:
1 + 2 + 3 + 4 + 5 == 5*(5+1)/2 == 5*6/2 == 30/2 == 15.

[gkieninger]

Ganz offensichtlich haben wir es hier mit der Summe der natürlichen Zahlen von 1 bis n zu tun. Und dafür ist die Formel n(n+1)/2. Also bei insgesamt 5 Nächten:
1 + 2 + 3 + 4 + 5 == 5*(5+1)/2 == 5*6/2 == 30/2 == 15.

Perfekt. Genau was ich brauche.
Ich habe die Routine schon, die mir die ganzen möglichen Übernachtungsblöcke ermittelt, aber damit kann ich jetzt auch meine Tests vereinfachen
Vielen Dank!

[gkieninger]

Unterbrechungen zählen also nicht? Ansonsten gibt es noch die Variante mit je einer Übernachtungen 1. und am 3.

Was meinst du mit Unterbrechungen?

[__blackjack__]

@gkieninger: Na genau was da steht. Übernachtung am 1., *nicht* am 2. und, aber am 3. Tag wäre ja theoretisch auch eine Möglichkeit die Du nicht ausgeschlossen hast, weil in den Randbedingungen nicht von Übernachtungen ”am Stück” die Rede ist. Das wären dann ``2**anzahl_naechte - 1`` Möglichkeiten, weil man die Nächte dann zum Beispiel als Bits sehen kann die gesetzt sind, wenn in der entsprechenden Nacht eine Übernachtung stattfindet. Eins abgezogen für die Bitkombination wo alle Nächte 0 ist.

[tonikae]

Mathematisch ist das was du willst (und wie du es beschrieben hast) nur eine einfache Fakultät (mathematisch: x!)
Ansonsten ist es Binominalkoeffizient (mathematisch: n über k)

Für alles gibt es Befehle. Sollte also keine große Sache sein.

[pillmuncher]

@tonikae: Nein, das ist es beides nicht. Lies meinen Beitrag weiter oben.

[gkieninger]

@gkieninger: Na genau was da steht. Übernachtung am 1., *nicht* am 2. und, aber am 3. Tag wäre ja theoretisch auch eine Möglichkeit die Du nicht ausgeschlossen hast, weil in den Randbedingungen nicht von Übernachtungen ”am Stück” die Rede ist. Das wären dann ``2**anzahl_naechte - 1`` Möglichkeiten, weil man die Nächte dann zum Beispiel als Bits sehen kann die gesetzt sind, wenn in der entsprechenden Nacht eine Übernachtung stattfindet. Eins abgezogen für die Bitkombination wo alle Nächte 0 ist.

Da hast du recht, ich war da ungenau, für mich wären das natürlich zwei Übernachtungen und nicht eine. Also Inanspruchnahme von zwei Möglichkeiten.
Aber die genannte Formel war einfach und hat auch bei meinen Tests einwandfrei funktioniert.