Pozitív egész többféle összegként

A lépcsős feladat legutóbb látott átfogalmazásában azt mondtuk, hogy a 6 számot írjuk fel egymást követő 1-esek és/vagy 2-esek összegeként.

Kis változtatással feltehetjük azt a kérdést is: hányféleképpen írható fel egy pozitív egész szám pozitív egész számok összegeként, ha megkülönböztetjük azokat az eseteket (is), amelyek csak a tagok sorrendjében különböznek.

Nem feltétlenül nyilvánvaló, hogy összesen 2^n-1 ilyen lehetőség van, ahogyan az sem kézenfekvő, hogy hogyan lehet ezek mindegyikét felsorolni. Erre ad megoldást a következő (meglepően rövid) rekurzív program.

A megoldás helyességének végiggondolását ezúttal rábízzuk az olvasóra: ha átesett az algoritmus megértésén, akkor jutalmul ölébe pottyan a lehetőségek számáról szóló fenti állítás bizonyításának alapgondolata is…

def part(k, n, sum):
    if   k<n:
        part(k+1, n, sum+[1])
        part(k+1, n, sum+[sum.pop()+1])
    elif k==n:
        print(sum, end=' ')

part(1, 5, [1])
print()

Az alább (áttördelve) megjelenített kimenet egyúttal szép illusztráció a lexikografikus rendezésre is.

[1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 2, 1] [1, 1, 3] [1, 2, 1, 1] [1, 2, 2] [1, 3, 1] [1, 4]
[2, 1, 1, 1] [2, 1, 2] [2, 2, 1] [2, 3] [3, 1, 1] [3, 2] [4, 1] [5]