如何在数组之间找到最大可能的匹配

Question

我有两个基于模块化的集群数组。

每个数组包含另一个数组2-7个名称--大名姓，因此数组中没有重复的名称，但是两个总体数组之间应该有重叠。

[[John, Mary], [Jane, Alex, Harry], [Rob, Sarah, Nadia]]  
[[Nadia, John, Mary], [Rob, Sarah, Eric], [Jane, Harry, Jake]]

我希望[Nadia, John, Mary]在输入[John, Mary]或[Rob, Sarah, Eric]时一定会被返回，或者在输入[Rob, Sarah, Nadia]时返回

在两个数组之间找到这样的最高可能匹配的最佳方法是什么？秩序不重要

Answer 1

您可以使用max和一个特殊的键函数，计算出现在第二个子列表中的第一个子列表中的元素。

for x in list1:
    y = max(list2, key=lambda y: sum(1 for w in x if w in y))
    print x, y

或者，由于顺序并不重要，而且一个子列表中的名称是唯一的，所以请使用集合列表并使用set交集：

    y = max(list2, key=lambda y: len(x & y))

Answer 2

在高级别上，我会将每个数组简化为二进制特征向量(如果没有给定的名称，则为0，如果是的话，则为1)，然后计算所有向量的成对余弦距离。距离最小的向量的名字最多。

或者，您可以查看一些局部性敏感散列方法。这听起来也像是家庭作业，所以我没有提供任何代码

Answer 3

我想您可以使用lambda作为max的key参数来计算相交元素的数量。

>>> s = ['John', 'Mary']
>>> max(l2, key = lambda i: len(set(s).intersection(i)))
['Nadia', 'John', 'Mary']

因此，您可以使用列表理解从第二个列表中生成一个与第一个列表一致的匹配列表。

>>> [max(l2, key = lambda i: len(set(j).intersection(i))) for j in l1]
[['Nadia', 'John', 'Mary'], ['Jane', 'Harry', 'Jake'], ['Rob', 'Sarah', 'Eric']]