如何在子集中找到python停止盎司目标产品？

Question

我一直在学习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 ---任意长度），也是如此。我希望脚本继续执行直到找到匹配为止。盎司找到了命中。它停止了，因为这将提高算法的速度。

下面的完整脚本

# 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 ounce 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

问题

如何使它起作用以提高算法速度？哪些Python技巧可以解决我的问题？有没有更短的方法？

Answer 1

将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。