python - 在 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.033 秒)。