Summenzerlegung

[Elgar]

Hiho,

ich muss mich im Moment gezwungenermaßen mit einer Summenzerlegung beschäftigen.

Eine gegebene Zahl ist in mehrere Summanden zu zerlegen.
Die Summanden können den Wert 2,3,4 oder 5 haben

Da sich da nun recht viele Kombinationen ergeben können und ich ungern das alles von Hand durchtippern möchte, suche ich nach einem Stückchen Code, das mir das ganze erleichtert, sei es nun für Excel, Java, C# oder meinetwegen auch Pseudocode.

Ein Beispiel:

Gegebene Zahl 19, 5 Summanden

Beispiel Lösungen wären dann ja z.B:

2,2,5,5,5
2,3,4,5,5
2,4,4,4,5
3,3,3,5,5
usw.

Schön wäre ein Lösung, bei der ich die Zahl, die Anzahl der Summanden und vorgegeben Werte der Summanden eingeben könnte.

Danke im Vorraus.

 

[Tornhoof]

Der Standardweg ist Rekursion dafür, eine ziemlich lange Erklärung findet sich hier: MP: Summenzerlegungen 2 (Matroids Matheplanet)

Du zerlegst rekursiv alle kleineren Werte bis zu deinem Wert, Anzahl der Summanden und notwendig vorhandene Elemente sind einfach Sonderfälle davon.

Beispiel: 5 in 3 Summanden

das beinhaltet also 4 in 2 Summanden + 1, 3 in 2 Summanden + 2, 2 in 2 Summanden + 3, 1 kannst du nicht in 2 ganzzahlige SUmmanden zerlegen.

Die eigentliche HErausforderung wäre sowas zu berechnen ohne viele doppelte Zerlegungen durchzuführen, also mit Lookuptabellen, dürfte für dich aber nicht relevant sein.

Zum Schluß kriegst du ne Tabelle raus mit den möglichen Summanden die deinen Wert zusammensetzen können. Davon erzeugst du, falls notwendig, noch alle Permutationen, wenn die Reihenfolge der Summanden relevant ist.