Получите n в точных k частях. Алгоритм рекурсии и разбиения. p (n, k)

Question

Я ищу, чтобы перечислить все разделы n в k частях.

Итак, для p (5,3) я получил бы 2 раздела k = 3 => (3,1,1), (2,2,1).

Вот что я нашел от поиска и просматривал 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 

^^^^ Это форма я хочу,

Как это, найти сумму к частям легко, вы возвращаете p (n-1, k-1) + p (nk, k). Что касается меня, мне нужно перечислить каждый элемент таким образом [(3,1,1), (2,2,1)].

Моя основная проблема - «построить» эти разделы рекурсивно. Как бы вы справились с этим?

Редактировать

Если вы получаете базовый случай к = 1, добавить + 1, к-1 раз. (4,1) затем (4,1,1)

Если вы получаете базовый блок k = n, разделите его и удалите по одному на каждую часть.

Как так: (3,3), а затем (3,3,3), а затем (2,2,2)

Если вы получите базовый случай к < п, ничего

В принципе, моя проблема состоит в том, чтобы «складывать» те из базового случая в верхнюю часть и получить полный список p (6,3) = [(2,2,2), (4,1,1), (3,2,1)]

Answer 1

Я хотел бы добавить к рекурсивной функции третьего параметра m, который представляет собой максимальное значение элемент может иметь в раздел. Тогда я бы определил функцию следующим образом:

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 

Примеры:

>>> 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)]