子集列表以添加到另一个列表中的元素
Subsetting a list to add up to elements in another list
有没有人对使用 python 解决以下问题的优雅代码和数学有一些想法？
我有两个数字列表：
A=[83.4,108,-240.2]
B=[10.3,96.7,-5.5,-20.4,30.9,2.1,-6.1,51.5,37.7,-25,-10.7,-250.4,-14.2,56.4,-11.5,163.9,-146.6,-2.6,7.9,-13.2]
我知道 B 可以分为三个包含 B 元素的列表，这样三个列表一起包含 B 中的所有元素，但三个列表没有重叠元素。这三个列表的总和就是A中的三个元素。
我会做蛮力法，就是把B的元素所有可能的组合分成三组，但是可能性的数量会随着B中元素的数量暴增。我也查看了背包问题，但这似乎只需要正值。
这确实是 subset sum problem 的变体：
In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.
An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s?
它是 NP 完全的证明：
The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it.
它是NP，因为它可以在多项式时间内验证：给定一个可能的解决方案，只需将子集中的数字相加，看看它们是否对应于A中的数字。并且，您可以在多项式时间内将子集问题简化为此问题：给定集合 x 和目标总和 s，让 A = [s, sum(x) - s] 和 B = x.
是NP-complete，一般情况下没有办法快速解决这个问题，使用Python或其他方式：
Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
正如@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 磨碎) 因此，由于我们需要访问具有这些长度的组合，我们可以使用字典理解来创建一个字典，其中分区长度作为键，组合作为值：
>>> all_combinations={i:combinations(B,i) for i in range(1,length-2)}
最后你需要得到基于subset_lenght项的组合，然后选择没有任何交集的组合，这些组合等于A中对应的项。
有没有人对使用 python 解决以下问题的优雅代码和数学有一些想法？
我有两个数字列表：
A=[83.4,108,-240.2]
B=[10.3,96.7,-5.5,-20.4,30.9,2.1,-6.1,51.5,37.7,-25,-10.7,-250.4,-14.2,56.4,-11.5,163.9,-146.6,-2.6,7.9,-13.2]
我知道 B 可以分为三个包含 B 元素的列表，这样三个列表一起包含 B 中的所有元素，但三个列表没有重叠元素。这三个列表的总和就是A中的三个元素。
我会做蛮力法，就是把B的元素所有可能的组合分成三组，但是可能性的数量会随着B中元素的数量暴增。我也查看了背包问题，但这似乎只需要正值。
这确实是 subset sum problem 的变体：
In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.
An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s?
它是 NP 完全的证明：
The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it.
它是NP，因为它可以在多项式时间内验证：给定一个可能的解决方案，只需将子集中的数字相加，看看它们是否对应于A中的数字。并且，您可以在多项式时间内将子集问题简化为此问题：给定集合 x 和目标总和 s，让 A = [s, sum(x) - s] 和 B = x.
是NP-complete，一般情况下没有办法快速解决这个问题，使用Python或其他方式：
Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
正如@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 磨碎) 因此，由于我们需要访问具有这些长度的组合，我们可以使用字典理解来创建一个字典，其中分区长度作为键，组合作为值：
>>> all_combinations={i:combinations(B,i) for i in range(1,length-2)}
最后你需要得到基于subset_lenght项的组合，然后选择没有任何交集的组合，这些组合等于A中对应的项。