python - Find all matchings of two differently sized arrays -

python - Find all matchings of two differently sized arrays -

so, have 2 different lists, say:

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

and goal find out minimum difference between these 2 lists. have defined function d(x,y) gives difference between 2 elements, x , y. match such: each element in list1 matches either 1 or 0 elements in list2. unmatched elements have "difference" given d(a).

i'm not sure best algorithm doing is, or how i'd go it. if it's relevant, i'm working in python.

i think want matching in bipartite graph: http://en.wikipedia.org/wiki/matching_(graph_theory)#maximum_matchings_in_bipartite_graphs should go matching algorithm. if can't lastly resort utilize integer programming. pulp suitable python bundle integer programming. integer programming bundle much slower perhaps easier code.

if take go integer programming, constraints variable aij represents connection between list1[i] , list2[j]. aij = 1 or 0. (connection either on or off). sum(aij on i) = 1. (one connection per element in list1). sum(aij on j) = 1 (one connection per element in list2). want maximize/minimize objective function sum(d(list1[i], list2[j])*aij). don't forget if length list1 != length list2, must add together variables allow variables connect cost d(x) , add together objective function.

python algorithm dynamic-programming