Rozkład liczby naturalnej

Question

Witam. Mam do napisania program, który dla dowolnej liczby naturalnej wypisuje wszystkie możliwe rozkłady tej liczby na liczby naturalne, np. dla n=7 ma wypisać:

• 7
• 6,1
• 5,2
• 5,1,1
• 4,3
• 4,2,1
• 4,1,1,1
• 3,3,1
• 3,2,2
• 3,2,1,1
• 3,1,1,1,1
• 2,2,2,1
• 2,2,1,1,1
• 2,1,1,1,1,1
• 1,1,1,1,1,1,1
  Kolejność liczb w kombinacji nie gra roli (nie trzeba wypisywać osobno 3,4 oraz 4,3). Dodatkowo mam za zadanie zliczyć, ile tych kombinacji jest. Nie mam żadnego pomysłu jak ten program zrobić. Próbowałam wykonać to tak, że najpierw wypisywałam pierwszą liczbę w kombinacji za pomocą pętli (od n do 1, zgodnie z powyższym przykładem) i do każdej tej liczby dobierałam kolejną, zakładając że nie będzie ona większa niż n/2 oraz będzie mniejsza lub równa w stosunku do pierwszej liczby. Jeśli te dwa składniki wciąż nie dawały razem wartości n, program dobierał dalej, sprawdzając czy suma jest już równa n. Pozwoliło to uzyskać częściowe rozwiązanie, jednak nie zwracało wszystkich możliwych kombinacji, gdyż nie uwzględniało przypadku, że np 2,2,2,1 można rozpisać dodatkowo jako 2,2,1,1,1, tylko od razu przechodziło do kombinacji 2,1,1,1,1,1.
  W związku z tym bardzo proszę o wskazówki jaką metodę mogłabym obrać. Moje pomysły się wyczerpały 

Comments

Trochę myślałem i taki algorytm prawdopodobnie byłby rekurencyjny oraz problemem byłoby to że odpowiedzi należałoby sprawdzać czy nie są zduplikowane (np 1+1+2 i 2+1+1 jest tym samym). Poczytałem na angielskim internecie i okazało się że te algorytmy wbrew pozorom są dość skomplikowane, głównie dlatego że ich złożoność bardzo, bardzo szybko rośnie - o ile liczbę 7 można rozłożyć w głowie, to np. 31 ma już zbyt dużo istniejących oraz duplikujących się kombinacji. Struktura set może się okazać pomocna bo nie przyjmuje duplikatów. Polecam poczytać, angielski termin to Partition

https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning
https://en.wikipedia.org/wiki/Partition_(number_theory)
https://stackoverflow.com/questions/2065553/get-all-numbers-that-add-up-to-a-number
https://stackoverflow.com/questions/28891477/recursive-function-counting-and-printing-partitions-of-1-to-n-1