如何检测相似的无序序列？

Question

我想在公路网中找到类似的交叉口。我的诀窍是找出最相似的街道名称序列。我已经创建了几个名字列表。其中一个是参考，另外两个是对应的。我想找一个街道名称和出现次数相同的。你知道吗

必须知道，名字的顺序不重要，重要的只是相似名字出现的次数。你知道吗

示例：

引用名称顺序：
[u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan']

邻居对应的名字顺序是：
{91: [u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan'], 142: [u'Tunnlandsgatan', u'Tunnlandsgatan', u' ']} 首先，我需要知道这个问题是否已经有了解决方案。第二，选择列表作为序列的容器是个好主意？最后，如果是，如何解决？你知道吗

我想正则表达式，但似乎没有任何用处，因为顺序是不固定的。你知道吗

Answer 1

如果创建每个键的引用的映射，然后在检查引用数组后减去引用，则可以确保得到正确的答案，即使该数组在映射中的顺序不正确

reference = [u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan']
sequence = {91: [u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan'], 142: [u'Tunnlandsgatan', u'Tunnlandsgatan', u' ']}
def getMatching(reference, sequence):
    for value in sequence.values():
        tempMap = {}
        for v in value:
            try:
                tempMap[v] += 1
            except KeyError:
                tempMap[v] = 1

        # tempMap now contains a map of the each element in the array and their occurance in the array
        for v in reference:
            try:
                # Everytime we find this reference in the 'reference' list, subtract one from the occurance
                tempMap[v] -= 1
            except:
                pass

        # Loop through each value in the map, and make sure the occurrence is 0
        for v in tempMap.values():
            if v != 0:
                break
        else:
            # This else statement is for the for loop, if the else fires, then all the values were 0
            return value
        continue
    return None

print getMatching(reference, sequence) # Prints [u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan']

现在如果你有这个，它仍然可以工作：

reference = [u'Barytongatan', u'Tunnlandsgatan', u'Barytongatan']
sequence = {142: [u'Tunnlandsgatan', u'Tunnlandsgatan', u' '], 91: [u'Barytongatan', u'Barytongatan', u'Tunnlandsgatan']}
print getMatching(reference, sequence) # Prints [u'Barytongatan', u'Barytongatan', u'Tunnlandsgatan'] even though they are not in the same order as reference