Найти K малейшие пары в двух списках

Question

Моя цель заключается в следующем:

1. пары элементов в двух списках; и
2. найти k мельчайшие пары.

На данный момент я могу пару каждый элемент в обоих списках на код ниже:

import itertools 

a = [1, 3, 5, 7] 
b = [2, 4, 6, 8] 
c = list(itertools.product(a, b)) 

print c 

И мой вывод:

[(1, 2), (1, 4), (1, 6), (1, 8), (3, 2), (3, 4), (3, 6), (3, 8), (5, 2), (5, 4), (5, 6), (5, 8), (7, 2), (7, 4), (7, 6), (7, 8)] 

Пусть я поставил k = 3, он должен вернуть мне три самые маленькие пары: (1, 2), (1, 4) и (3, 2). Как мне это сделать?

Answer 1

Вы можете использовать heapq.nsmallest с sum в качестве ключевой функции:

>>> import heapq 
>>> heapq.nsmallest(3,c,key=sum) 
[(1, 2), (1, 4), (3, 2)] 

Или, как @jonrsharpe сказал в комментарии вы можете использовать sorted:

sorted(c, key=sum)[:k]