0

假设我有一个列表，x=[1, 2, 3, 4]它包含子列表[1]、[2]、[3]、[4]、[1, 2]、[2, 3]、[3, 4]、[1,2,3]和。但它不包含类似的东西，因为在 x 中 2 出现在 1 和 3 之间时存在间隙。[2,3,4][1,2,3,4][1, 3]

有谁知道最好的方法是测试一个列表是否包含在另一个列表中而没有间隙？我曾想过一个 for-loop 解决方案，但它可能不是一个很好的解决方案。谢谢。

4

5 回答 5

3

你的问题是：

有谁知道最好的方法是测试一个列表是否包含在另一个列表中而没有间隙？

这实际上与在另一个字符串中查找字符串的问题相同。为此，您有大量可用的算法。

Rabin-Karp、Boyer-Moore、Knuth-Morris 等。我喜欢 Boyer-Moore，因为它简单。在互联网上查看详细信息。当然，您也可以检查您的列表是否从任何可能的位置开始，但复杂性不是最佳的（您可以在这里找到这样的解决方案：检查 Python 中是否存在切片列表）。

这是一个快速（和简化）的实现：

def boyer(x, sublist):
    p = len(sublist) - 1
    i = 0
    while i + p < len(x):
        if x[i + p] == sublist[p]:
            if p == 0:
                return True
            p -= 1
        elif x[i + p] in sublist:
            i += 1
            p = len(sublist) - 1
        else:
            i = i + p + 1
            p = len(sublist) - 1
    return False

请注意，应仔细测试此代码，并且更多地是关于显示暴力方法的替代方法。的时间复杂度x[i + p] in sublist是线性的，应该以不同的方式实现以获得 O(1) 方法。目前，正因为如此，它不会比蛮力方法更好。

于 2014-01-19T14:01:54.010 回答
2

你可以试试

' '.join(str(c) for c in list1) in ' '.join(str(c) for c in list2)
于 2014-01-19T14:12:03.230 回答
1 
sequences = [
    [1], [2],
    [1, 2], [2, 3], [3, 6],
    [1, 2, 3], [2, 3, 4], [1, 2, 3, 5],
]

bad_seq = lambda s: s and s != list(range(s[0], s[0] + len(s)))
print filter(bad_seq, sequences)   # [[3, 6], [1, 2, 3, 5]]
于 2014-01-19T14:55:43.397 回答
0

You can use numpy-diff function on indices of the sublist in the main list

In [427]: x=[1, 2, 3, 4]

In [428]: y = [1,3]

In [429]: z = [1,2,3]

In [430]: w = [2,1]

In [431]: import numpy as np

In [432]: sub_indices = [x.index(x1) for x1 in y]

Now, sub_indices should look like: [0, 2] So you can check the diff between the indices:

In [433]: np.all(np.diff(sub_indices) == 1)
Out[433]: False

In [434]: sub_indices = [x.index(x1) for x1 in z]

In [435]: np.all(np.diff(sub_indices) == 1)
Out[435]: True

In [436]: sub_indices = [x.index(x1) for x1 in w]

In [437]: np.all(np.diff(sub_indices) == 1)
Out[437]: False
于 2014-01-19T14:55:58.367 回答
0

只是另一种解决方案，不确定同类中最好的，如果我不清楚您的问题，请告诉我。

ls = [[1], [2], [3], [4], [1, 2], [2, 3], [3, 6], [1, 2, 3], [2, 3, 4], [1, 2, 3, 5]]

def gap(l):
    for ls in l:
        result = list(set(map(lambda x: x[1] - x[0], zip(ls[0:], ls[1:]) )))
        if result and (len(result) > 1 or result[0] > 1):
            print ls
gap(ls)

输出：[3,6] [1, 2, 3, 5]

于 2014-01-19T14:40:03.517 回答