如何找到尽可能多和完整的列表分区

Question

例如：

list1 = [5,8]
list2 = [4,4,2,3,6]

使用电源设置功能可以轻松获得 5 和 8 在list2

的组合

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

8 可以由 [4,4] 或 [2,6] 组成，但 5 只能由 [2,3] 组成。如果我选择 8 的 [2,6] ，list2 中没有 5 的组合。

我怎样才能获得 8 [4,4]和 5 [2,3]？ 我想为list1中的数字选择尽可能多的组合list2.实际上，list1中的数字可能由 3 个或更多 list2 中的数字组成。

实际问题更困难，因为可能有一些数字未在list1中使用，而list1中的数字可能由 3 个或更多数字组成。

Answer 1

我认为这可以满足您的需求：

list1 = [5,8]
list2 = [4,4,2,3,6]

for i in list2:
    for j in list2:
        if i+j in list1:
            print("%d + %d = %d"%(i, j, i+j))

它

尝试创建每个可能的添加，如果它包含在第一个列表中，则输出它。

输出：

4 + 4 = 8
4 + 4 = 8
4 + 4 = 8
4 + 4 = 8
2 + 3 = 5
2 + 6 = 8
3 + 2 = 5
6 + 2 = 8

Answer 2

这是一个简洁有效的方法。

import itertools
def combos(a, b):
    matches = []
    for combo in list(itertools.combinations(a, 2)):
        if combo[0] + combo[1] in b:
            matches.append(combo)
return matches    
>> [(4, 4), (2, 3), (2, 6)]

这是另一种方式：

def foo(matches, *args):
    matches_dict = {k: [] for k in matches}
    for _, tup in enumerate(*args):
        if sum(tup) in matches:
            matches_dict[sum(tup)].append(tup)
    return matches_dict
>> {5: [(2, 3)], 8: [(4, 4), (2, 6)]}

现在计时：

time combos(list2, list1)
CPU times: user 23 µs, sys: 7 µs, total: 30 µs
Wall time: 31 µs
time foo(list1, list(itertools.combinations(list2, 2)))
CPU times: user 33 µs, sys: 9 µs, total: 42 µs
Wall time: 40.1 µs

使用@moritzg答案，修改为不包括重复，

def fizz(list1, list2):
    matches = []
    for i in list2:
        for j in list2:
            if i+j in list1:
                matches.append((i,j))
    return set(matches)
time fizz(list1, list2)
CPU times: user 26 µs, sys: 13 µs, total: 39 µs
Wall time: 35 µs

另外，我忘了提到(2,6)是否与您不同(6,2)尽管不应该，但您可以将itertools.combinations切换到itertools.permutations。