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

Question

例如：

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

这是很容易通过使用powerset函数

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]得到在list2的5和8的组合，但5只能是由[2,3]组成。如果我选择[2,6]为8，则list2中没有5的组合。

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

实际问题比较困难，因为可能有一些数字在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。