在Python中仅一次使用数字进行整数分区的递归比较慢

Question

我正在尝试在Python 2.7中仅使用一次将每个数字相加即可得出一个单一值的可能组合数。

例如，对于7，这将是6 + 1、5 + 2、4 + 3、4 + 2 + 1-> 4种可能的组合

我设法将其伪装成一个数学正确的递归函数

import time

counter_list = []

def start(n):
    tic=time.time()
    recursive_step(range(1, n), n)
    toc=time.time()
    print(toc - tic)
    return len(counter_list)

def recursive_step(numbers, target, summe=0):

    if summe == target:
        counter_list.append(1)
    if summe >= target:
        return

    for i in xrange(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        recursive_step(remaining, target, summe + n)

if __name__ == "__main__":
    print(start(7))

不幸的是，当数字变大时，它变得非常慢。以下是我在机器上测量过的一些数字。

~~~ 40 ~~~
time in seconds:        0.0789999961853
possible combinations:  1112
~~~ 50 ~~~
time in seconds:        0.40299987793
possible combinations:  3657
~~~ 60 ~~~
time in seconds:        1.51200008392
possible combinations:  10879
~~~ 70 ~~~
time in seconds:        5.41400003433
possible combinations:  29926
~~~ 80 ~~~
time in seconds:        18.388999939
possible combinations:  77311
~~~ 90 ~~~
time in seconds:        54.5920000076
possible combinations:  189585

我研究了动态编程原理。但是我无法解决该问题。任何有关如何改进该脚本的建议将不胜感激

Answer 1

此顺序的参考：http://oeis.org/A000009

您可以将n划分为不同的部分的问题看作是硬币替换问题，其中硬币的值（单个）为1到n。 （或者比这少一个，因为似乎不允许将n的分区作为单个数字n。）>

您可以通过改编标准的硬币找零动态编程解决方案来计算解决方案。

def Q(n):
    A = [1] + [0] * n
    for i in range(1, n+1):
        for j in range(n, i-1, -1):
            A[j] += A[j-i]
    return A[n] - 1

print(Q(500))
您可以通过注意到在外循环的k迭代后，A[i]包含用i中的不同元素对1..k进行分区的方式来理解该程序。并且用i中的不同元素划分1..k+1的方式数是i中的不同元素划分1..k的方式数加上i-k-1中的元素划分1..k的方式数]。

这以O（n ^ 2）的时间运行，但是在小情况下运行速度很快（例如：这里的500个分区，在我的机器上需要0.033s的时间。