我一直在学习 Python,因为我的爱好和对 NP 完全问题(例如子集产品)的实证研究。我的算法有效,但它并没有按照我打算的方式进行。
我想要做的是停止 itertools 的 combinations
一旦它到达输入变量 target
的子集乘积.这将稍微使代码更快。代码处于完善阶段所以有一个不必要的列表res_2
这是循环。
res_2 = [];
for i in range(1, len(s)+1):
var = (findsubsets(s, i))
kk = list(map(numpy.prod, var))
res_2.append(kk)
if target in kk:
print('yes')
print(var)
break
这是我不想要的输出。请注意,脚本不会在 (4, 4) 处停止。一旦“命中”目标,继续检查所有组合是一种资源浪费。
Enter numbers WITH SPACES: 4 4 3 12
enter target integer:
16
yes
[(4, 4), (4, 3), (4, 12), (4, 3), (4, 12), (3, 12)]
kk
[16, 12, 48, 12, 48, 36]
我的预期输出是在 (4, 4) 处停止,如果它是第一次“命中”。对于任何其他子集(如 (1,2,3) 或 (1,2,3---any-length))也是如此。我更喜欢脚本是否继续,直到它能够找到命中。一旦找到命中,它就会停止,因为这会提高算法的速度。
完整脚本如下
# Naive Subset-Product solver
# with python's itertools
import itertools
import numpy
s = list(map(int, input('Enter numbers WITH SPACES: ').split(' ')))
print('enter target integer: ')
target = int(input())
if s.count(target) > 0:
print('yes')
quit()
if target > numpy.prod(s):
print('sorry cant be bigger than total product of s')
quit()
def findsubsets(s, n):
return list(itertools.combinations(s, n))
# Driver Code
n = len(s)
# This code snippet is a for loop. It also is intended to cut down execution
# time once it finds the target integer. (instead of creating all combinations)
res_2 = [];
for i in range(1, len(s)+1):
var = (findsubsets(s, i))
kk = list(map(numpy.prod, var))
res_2.append(kk)
if target in kk:
print('yes')
print(var)
break
题
我如何让它工作以提高算法的速度?什么 Pythonic 技巧可以解决我的问题?有没有更短的方法来做到这一点?
最佳答案
转换 itertools 的 combinations
为时尚早返回值变成 list
,尤其是当您尝试提前退出并避免过多开销时。库函数返回迭代器而不是完全实现的列表通常是有充分理由的。
这是一个建议:
def findsubsets(s, n):
return itertools.combinations(s, n)
def find_subset(target,nums):
for i in range(1,len(nums)+1):
for ss in findsubsets(nums, i):
if np.prod(ss) == target:
prodstr = '*'.join(str(num) for num in ss)
print(f"{target} = {prodstr}")
return ss
return None
find_subset(96,[1,6,2,8])
鉴于
findsubsets
是一行,将它作为一个独立的函数是有问题的(我们基本上只是别名 combinations
,这可以用 import X as Y
语句完成)。在任何情况下,这都应该尽早停止,而不会因较大的输入而占用过多的 RAM。
关于python - 一旦在子集中找到目标产品,如何让python停止?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58925664/