python - 在 Python 中仅使用一次数字进行整数分区的递归很慢
问题描述
我正在尝试在 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
我研究了动态编程原理。但我无法让它解决这个问题。任何关于如何改进该脚本的建议将不胜感激
解决方案
关于这个序列的参考: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 秒)。
推荐阅读
- php - 如何使用 PHP 函数使用 PDO 连接到 MySQL
- windows-10 - Pyplot 不适用于 Pyinstaller。exe崩溃没有错误
- python - 如何去除附着在另一个大轮廓上的小轮廓
- python - python 中的进程是否有自己的 os.environ 副本?
- python - 在 excel 文件中加载工作表并将其保存到另一个不同的 excel 文件
- asp.net - 在 ASP.NET 和经典 ASP 之间共享会话状态
- android - 如何检测设备是否获取我的手机蓝牙名称?
- javascript - 无法弄清楚如何等待 Promise
- r - 创建给定矩阵
- c# - 代码没有返回预期值?