0

所以，我有两个不同的列表，比如说：

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

我的目标是找出这两个列表之间的最小差异。我有一个定义的函数d(x,y)，它给出了两个元素之间的区别，x并且y. 它们是这样匹配的：list1 中的每个元素都匹配 list2 中的一个或零个元素。不匹配的元素也具有由 给出的“差异” d(a)。

我不确定这样做的最佳算法是什么，或者我将如何去做。如果它是相关的，我正在使用 python。

4

3 回答 3

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。（连接打开或关闭）。Sum(Aij over i) = 1。（list1 中每个元素一个连接）。Sum(Aij over j) = 1（list2 中每个元素一个连接）。现在你想最大化/最小化目标函数 sum(d(list1[i], list2[j])*Aij)。不要忘记如果长度列表 1 ！= 长度列表 2，您必须添加额外的变量以允许某些变量以成本 d(x) 连接到自身并将其添加到目标函数中。

于 2013-02-13T10:16:06.710 回答
0

我认为这个问题有点含糊，但我的想法如下：

尽管我想知道 OP 是否正在寻找列表或类似产品的产品。

也许如果 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]
于 2013-02-13T11:30:03.497 回答
0

我不太确定您要问的基本上是找到两个列表之间共有的所有元素。

在这种情况下，这可能有效：

list1 = [1,2,3,4]
list2 = [3,4,5]
diff = set(list1).intersection(set(list2))
于 2013-02-13T10:20:45.220 回答