Zdobądź n w dokładnych częściach k. Algorytm rekursji i podziału. p (n, k) - python, rekursja, integer-partycja

Szukam wyliczyć wszystkie partycje n na części.

Tak więc dla p (5,3) otrzymam 2 partycje k = 3 => (3,1,1), (2,2,1).

Oto co znalazłem od przeszukiwania i przeglądania przez stackoverflow:

def p(n,k):
lst = []
if n < k:
return lst
elif k == 1:
return lst
elif k == n:
return lst
else:
p(n-1, k-1)
p(n-k, k)
return lst

^^^^ To jest forma, którą chcę,

Jak już jest, znalezienie sumy k części jest łatwe, zwracasz p (n-1, k-1) + p (n-k, k). Jeśli chodzi o mnie, muszę podać każdy element w taki sposób [(3,1,1), (2,2,1)].

Moim głównym problemem jest "kompilacja" tych partycji rekurencyjnie. Jak poradziłbyś sobie z tym?

Edytować

Jeśli otrzymasz skrzynkę podstawową k = 1, dodaj + 1, k-1 razy. (4,1) wtedy (4,1,1)

Jeśli otrzymasz skrzynkę podstawową k = n, podziel ją i usuń jedną do każdej części.

Podobnie jak: (3,3) wtedy (3,3,3), a następnie (2,2,2)

Jeśli otrzymasz podstawowy przypadek k <n, nic

Zasadniczo, moim problemem jest "ułożenie" tych z podstawówki na górę i uzyskanie kompletnej listy p (6,3) = [(2,2,2), (4,1,1), (3,2 , 1)]

Odpowiedzi:

2 dla odpowiedzi № 1

Dodałbym do funkcji rekursywnej trzeci parametr m która jest maksymalną wartością elementu w partycji. Następnie zdefiniowałbym taką funkcję:

def p(n, k, m=None):
if m is None:
m = n - k + 1 # maximum can be n - k + 1 since minimum is 1
if k == 0:
if n == 0:
yield ()
return
for i in xrange(1, m + 1): # first could be from 1 to the maximum
# the rest of the sum will be n - i among k - 1 elements with
# maximum i
for t in p(n - i, k - 1, i):
yield (i, ) + t

Przykłady:

>>> list(p(10, 3))
[(4, 3, 3), (4, 4, 2), (5, 3, 2), (5, 4, 1), (6, 2, 2), (6, 3, 1), (7, 2, 1), (8 , 1, 1)]
>>> list(p(6, 2))
[(3, 3), (4, 2), (5, 1)]

---