如何找到儘可能多且儘可能完整的分區列表？

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。