时间戳

首页 > 解决方案 > 找出可能达到结果的整数组合的数量

python - 找出可能达到结果的整数组合的数量

问题描述

我有点卡在python问题上。

我想写一个函数，它接受一个正整数 n 并返回不同操作的数量，这些操作可以和 n (2<n<201) 并带有递减和唯一的元素。举个例子：如果 n = 3 那么 f(n) = 1（因为唯一可能的解决方案是 2+1）。如果 n = 5，则 f(n) = 2（因为可能的解是 4+1 和 3+2）。如果 n = 10 那么 f(n) = 9 （因为可能的解是 (9+1) & (8+2) & (7+3) & (7+2+1) & (6+4) & ( 6+3+1) & (5+4+1) & (5+3+2) & (4+3+2+1))。

对于我这样开始的代码：

def solution(n):
nb = list(range(1,n))
l = 2
summ = 0
itt = 0
for index in range(len(nb)):
    x = nb[-(index+1)]
    if x > 3:
        for index2 in range(x-1):
            y = nb[index2]
            #print(str(x) + ' + ' + str(y))
            if (x + y) == n:
                itt = itt + 1
            for index3 in range(y-1):
                z = nb[index3]
                if (x + y + z) == n:
                    itt = itt + 1
                for index4 in range(z-1):
                    w = nb[index4]
                    if (x + y + z + w) == n:
                        itt = itt + 1
                   
return itt

它在 n 很小的时候起作用，但是当你开始在 n=100 左右时，它非常慢，我需要添加更多的 for 循环，这会使情况恶化......

你知道我该如何解决这个问题吗？我错过了一个明显的解决方案吗？

标签： pythonmath

解决方案

这个问题被称为整数分割成不同的部分。OEIS 序列（值减 1，因为您不需要n=>ncase ）

我已经有了将分区划分为 k 个不同部分的代码，因此对其进行了一些修改以将分区数计算为任意数量的部分：

import functools

@functools.lru_cache(20000)
def diffparts(n, k, last):
    result = 0
    if n == 0 and k == 0:
            result = 1
    if n == 0 or k == 0:
        return result

    for i in range(last + 1, n // k + 1):
        result += diffparts(n - i, k - 1, i)
    return result

def dparts(n):
    res = 0
    k = 2
    while k * (k + 1) <= 2 * n:
        res += diffparts(n, k, 0)
        k += 1
    return res

print(dparts(201))

推荐阅读