4

我知道这个问题可能看起来像重复。但我很难解决这个问题，我找不到对我的案例有用的解决方案

我正在使用 python 实现一个遗传算法来解决旅行商问题

假设我们有这些列表（旅游）

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]

如您所见，[5,4] 在整个 3 个列表中重复，常规交集将返回列表中的所有元素。

我想要一些函数，比如 intersect_list(a,b)

返回 [5,4]

有没有内置的python方法来找到这个？或者你有什么建议吗？

注意：我知道我可以循环它来解决这个问题，但请记住，就我而言，我有大约 400 个列表。每个长度为 401。

换句话说：我想看看这些列表之间的共同路径。

请让我知道是否有任何不清楚的地方提前谢谢。

4

4 回答 4

3

在查看了@pyfunc 发布的链接后，我想到了以下内容：

def shortest_of(lists):
    return min(lists, key=len)

def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1)) 

def longest_common(lists):
    if not lists:
        return ()
    res = set()    
    base = shortest_of(lists)
    length = len(base)

    for i in xrange(length, 0, -1):
        for j in xrange(length - i + 1):
            candidate = ', ' + str(base[j:i+j]).strip('[]') + ','
            #candidate = base[j:i+j]  

            for alist in lists:
                if not candidate in ', ' + str(alist).strip('[]') + ',':
                #if not contains_sublist(alist, candidate):   
                    break
            else:
                res.add(tuple([int(a) for a in candidate[2:-1].split(',')]))
                #res.add(tuple(candidate))

        if res:
            return tuple(res)    

    return ()

if __name__ == '__main__':
    a = [1,0,2,5,4,3,1]
    b = [1,2,5,4,3,0,1]
    c = [1,3,5,4,2,0,1]

    print longest_common([a,b,c])
    print longest_common([b,c])

输出：

((5, 4),)
((0, 1), (5, 4))

编辑：

更新了使用字符串转换和匹配的解决方案，因为它恰好更快。以前的解决方案部分已被注释掉。此外，它现在提供了所有可能性。

于 2012-06-08T02:25:43.797 回答
1

一个想法是，您可以将列表转换为字符串

",".join(list)

然后将问题转换为两个字符串中最长匹配的子字符串。

解决方案和讨论在 SO 上有：

  1. 来自两个以上字符串的最长公共子字符串 - Python
  2. http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python
于 2012-06-08T00:10:42.980 回答
1

400 个长度为 400 的列表并不是什么大问题。首先将每个序列分解为所有可能的子序列（长度列表N围绕0.5 * N ** 2可能的子序列）。然后将它们全部相交并取最长的一个。

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]

def longest_match_finder(lists):
    matches = []
    for a in lists:
        lengths = set()
        for leng in xrange(1,len(a)+1):
            lengths = lengths | set(tuple(a[i:i+leng]) 
                                    for i in xrange(len(a)-leng+1))
        matches.append(lengths)
    return max(set.intersection(*matches), key=len)

print longest_match_finder([a,b,c])
#Output:
(5, 4)

使用400每个带有400元素的列表，这需要280 seconds（在我非常旧的机器上）。但是，如果我们仅在一个列表上使用相同的方法，但将其子序列以及所有其他列表转换为字符串（如 @pyfunc 首次发布的那样），使用str(list).strip('[]')，我们可以更快地搜索。相同的测试运行在21 seconds：

import ast

def longest_match_finder_2(lists):
    a = lists[0]
    lengths = set()
    for leng in xrange(1,len(a)+1):
        lengths = lengths | set(str(a[i:i+leng]).strip('[]') 
                                for i in xrange(len(a)-leng+1))
    for seq in lengths.copy():
        if not all([seq in str(i).strip('[]') for i in lists[1:]]):
            lengths.remove(seq)
    return ast.literal_eval(max(lengths, key=len))

我们可以ast.literal_eval()在最后（安全地）使用来获取列表。

于 2012-06-08T00:46:12.720 回答
-1

您可以使用 list zip函数将它们压缩成元组并返回所有元素都相同的元组。

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]
zipped_tuples = zip(a, b, c)

您可以尝试利用它来获取位置交叉点。

于 2012-06-08T00:18:21.360 回答