子集列表以添加到另一列表中的元素

这确实是 subset sum problem :

在里面 computer science 这个 子集和问题 是 complexity theory 和 cryptography 问题是:给定一组(或多组)整数,是否存在和为零的非空子集?例如,给定集合{7,3,2,5,8},答案是 对 因为子集{3,2,5}和为零。问题是 NP-complete .

一个等价的问题是:给定一组整数和一个整数 s ,任何非空子集的总和是否为 s ?

证明它是NP完全的:

证明某个新问题是NP完全的最简单方法是首先证明它在NP中,然后将一些已知的NP完全问题简化为它。

它在NP中,因为它可以在多项式时间内验证:给定一个潜在的解决方案,只需将子集中的数字相加,看看它们是否与 A 。而且,可以在多项式时间内将子集问题简化为这个问题:给定集合 x 和目标总和 s 允许 A = [s, sum(x) - s] 和 B = x .

它是 NP完成 ,在一般情况下,无法使用Python或其他方式快速解决此问题:

尽管NP完全问题的任何给定解都可以很快(在多项式时间内)得到验证,但没有已知的有效方法可以首先找到解;事实上,NP完全问题最显著的特点是不知道它们的快速解。也就是说,使用任何当前已知的方法解决问题所需的时间 algorithm 随着问题规模的增长,增长速度非常快。因此,确定是否有可能快速解决这些问题,称为 P versus NP problem ,是校长之一 unsolved problems in computer science 今天

正如@Claudiu很好地解释的那样,这些问题是NP完全的,你不能以有效或一般的方式来解决它们,但在这种情况下,作为一种特殊而不太有效的方式,你可以发挥作用 itertools 模块如下:

>>> from itertools import combinations,product,chain

>>> length=len(B)
>>> subset_lenght=[(i,j,k) for i,j,k in combinations(range(1,length),3) if i+j+k==length]
>>> all_combinations={i:combinations(B,i) for i in range(1,length-2)}
>>> for i,j,k in subset_lenght:
...     for t,p,m in product(all_combinations[i],all_combinations[j],all_combinations[k]):
...         if not set(t)&set(p)&set(m) and map(sum,(t,p,m))==A:
...            print chain.fromiterable(t,p,m)

在这种方法中,首先您需要所有可能的长度,这些长度之和等于您的主要列表长度,为此,您可以使用以下列表理解:

>>> [(i,j,k) for i,j,k in combinations(range(1,len(B)),3) if i+j+k==len(B)]
[(1, 2, 17), (1, 3, 16), (1, 4, 15), (1, 5, 14), (1, 6, 13), (1, 7, 12), (1, 8, 11), (1, 9, 10), (2, 3, 15), (2, 4, 14), (2, 5, 13), (2, 6, 12), (2, 7, 11), (2, 8, 10), (3, 4, 13), (3, 5, 12), (3, 6, 11), (3, 7, 10), (3, 8, 9), (4, 5, 11), (4, 6, 10), (4, 7, 9), (5, 6, 9), (5, 7, 8)]

然后,您需要获取长度为1到 len(main_list)-3 (在本例中为17,但由于范围不包含最后一个数字,我们将把数字1放得更大)因此,由于我们需要访问这些长度的组合,我们可以使用dict理解来创建一个以分区长度为关键字、以组合为值的字典:

>>> all_combinations={i:combinations(B,i) for i in range(1,length-2)}

最后你需要根据 subset_lenght 项目,然后选择没有交集的项目,并且这些总和等于中的相应项目 A .