Количество способов разбить число в Python

Question

Я определил рекурсивную функцию, которая принимает число n и возвращает list списков чисел, которые суммируются с этим числом (разделы):

def P(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    for p in P(n-1):        
        p.append(1)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p

Мне было интересно, как заставить функцию возвращать число разделов для номера n.

Например, P(6) вернет 10.

Answer 1

Если вы посмотрите на раздел «Формулы функций разбиения» на странице Partiton (теория чисел) в Википедии, вы увидите, что не существует простого способанайдите номер раздела.

Вместо этого, вероятно, лучше всего сделать ставку:

sum(1 for _ in P(6))

или, что несколько проще, но слишком много памяти для больших чисел

len(list(P(6)))

с использованием существующегоfunction.

Также обратите внимание, что если вы хотите сохранить значения, возвращаемые P, вы должны быть yield ing p[:], а не p - вы хотите сделать копию, а невыводить один и тот же список (который вы меняете) снова и снова.Вы можете понять, почему, если вы делаете list(P(6)) - он возвращает список того же самого пустого списка, повторяемого снова и снова .

Для получения дополнительной информации о разбиении см. Разделение с помощьюPython .

Answer 2

Вот пример на Java для вычисления желаемого результата.

/**
 * Returns the number of ways the number n can be partitioned
 * into sums of positive integers larger than k. 
 * @param k
 * @param n
 * @return
 */
public static long partition(long k, long n){
    long sum = 0;
    if(k > n) return 0;
    if(k == n) return 1;
    sum += partition(k+1, n) + partition(k, n-k);
    return sum;
}