Найти все паросочетания двух разных размеров массивов

Question

Таким образом, у меня есть два разных списка, скажем:

list1 = [a,b,c,d] 
list2 = [e,f,g] 

И моя цель состоит в том, чтобы выяснить минимальную разницу между этими двумя списками. У меня есть определенная функция d(x,y), которая дает разницу между двумя элементами, x и y. Они соответствуют таковым: каждый элемент в списке1 соответствует одному или нулевому элементу в списке2. Непревзойденные элементы также имеют «разницу», заданную d(a).

Я не уверен, какой лучший алгоритм для этого, или как я буду заниматься этим. Если это актуально, я работаю на python.

Answer 1

Я думаю, вы хотите совпадение на двухстороннем графике: http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs Вы должны пойти с алгоритмом сопоставления. Если вы не можете в качестве последнего средства использовать целочисленное программирование. Pulp - подходящий пакет python для целочисленного программирования. Программный пакет Integer будет намного медленнее, но, возможно, проще кодировать.

Если вы решите пойти с помощью программирования целых чисел, ограничения заключаются в том, что переменная Aij представляет собой соединение между list1 [i] и list2 [j]. Aij = 1 или 0. (соединение включено или выключено). Сумма (Aij над i) = 1. (одно соединение для элемента в списке1). Сумма (Aij над j) = 1 (одно соединение на элемент в списке2). Теперь вы хотите максимизировать/минимизировать сумму целевой функции (d (list1 [i], list2 [j]) * Aij). Не забудьте, если длина list1! = Length list2, вы должны добавить дополнительные переменные, чтобы некоторые переменные могли подключаться к себе со стоимостью d (x) и добавлять их к целевой функции.

Answer 2

Я не совсем уверен, что то, что вы просите, это в основном найти все элементы, которые являются общими между двумя списками.

В этом случае, это может работать:

list1 = [1,2,3,4] 
list2 = [3,4,5] 
diff = set(list1).intersection(set(list2)) 

Answer 3

Я думаю, что вопрос немного расплывчато, но мой удар в нем будет следующее:

Хотя мне интересно, если ОП ищет для продукта списков или аналогичных.

Возможно, если OP просмотрел itertools-functions, они могли бы видеть что-то подходящее.

import random 

list1 = random.sample(range(50), 3) 
list2 = random.sample(range(50), 2) 

print "List1", list1 
print "List2", list2 


def router(a, b): 
    print "ROUTER", a, b 
    if a == None: 
     return b * 10 
    elif b == None: 
     return a * 10 
    else: 
     return (a + b) * 10 


print map(router, list1, list2) 

########################## 
# Using itertools.product 
########################## 
import itertools 

def pair(p): 
    a, b = p 
    print "PAIR", a, b 
    if a == None: 
     return b * 10 
    elif b == None: 
     return a * 10 
    else: 
     return (a + b) * 10 

product = itertools.product(*zip(*map(None, list1, list2))) 

print map(pair, product) 

Выходные

List1 [17, 48, 9] 
List2 [45, 42] 
ROUTER 17 45 
ROUTER 48 42 
ROUTER 9 None 
[620, 900, 90] 
PAIR 17 45 
PAIR 17 42 
PAIR 17 None 
PAIR 48 45 
PAIR 48 42 
PAIR 48 None 
PAIR 9 45 
PAIR 9 42 
PAIR 9 None 
[620, 590, 170, 930, 900, 480, 540, 510, 90]