如何检查一个列表是否按顺序是另一个列表的子序列

Question

如何检查一个列表是否按顺序是另一个列表的子序列

3

我有一个列表 input:

[1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 2, 7, 1, 7, 2, 1]

我需要检查 lookup_list [1,2,3,4,5,7,8,9,5,4,3,2,1] 的元素是否以相同的顺序在另一个列表中以分散的方式存在。

下面的内容将说明我的意思：

[1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 2, 7, 1, 7, 2, 1]

加粗的数字是 lookup_list 中的数字，它们在 input 列表中的顺序相同，但也有其他无关项在它们之间。

有没有办法可以检查这个问题？

这是我尝试的方法：

count = 0
a = 0
indices = []
for item in list:
    idx = -1
    if count < len(input_list):
        idx = list.index(input_list[count])
        if idx != -1:
            a = a +len(list[:idx])
            list = list[idx:]
            indices.append(a + idx)
    count = count +1
print(indices)

但是它给了我以下结果：

[0, 2, 5, 35, 25, 24, 33, 30, 33, 37, 38, 64, 54]

问题在于，此方法未维护lookup_list的顺序。

- user150599

你的问题确切是什么？“我有没有办法检查这个？” - deadshot

4

看起来已经很清楚了：如何确定序列相等而跳过非共同元素。话虽如此，这可以通过嵌套循环来完成：是否有任何工作开始？只需重复“用笔和纸”解决它的步骤。如何用文字/点阵步骤解释这个笔和纸算法？ - user2864740

嗨@deadshot，是的，user2864740是正确的，我想知道是否有任何方法可以在跳过非相关元素并保持lookup_list中的顺序的情况下，在输入列表中检查lookup_list中的项目。 - user150599

1

你能想到一个逐步进行的手动测试过程吗？ - Karl Knechtel

3个回答

1

def check_exists(l, lookup_list):
check = True
for i in lookup_list:
    try:
        index = l.index(i) 
        l = l[index+1:]
    except ValueError:
        check = False 
        break 
return check

check_exists() 函数将完整列表和查找列表作为参数，并在序列存在时返回 True，不存在时返回 false。

以下是完整程序 -

def check_exists(l, lookup_list):
    check = True
    for i in lookup_list:
        try:
            index = l.index(i) 
            l = l[index+1:]
        except ValueError:
            check = False 
            break 
    return check



l = [1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 
4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 
2, 7, 1, 7, 2, 1]
lookup_list = [2,3,4,5,7,8,9,5,4,3,2,1] 

print(check_exists(l,lookup_list))

- Indrajeet Singh

1

我喜欢使用 l.index 的想法 - 而且你的方法显然可行 - 但是，你可以利用 l.index 接受第二个可选参数的事实，该参数是起始索引，并使用从上一次保存的 index 值 - 即 index = l.index(i, index) + 1。（将 index 初始化为0。） - alani

有道理，Alaniwi。我会修改它。谢谢。 - Indrajeet Singh

1

@SindhuSatish兄弟，不要忘记按照alaniwi的评论更新它。 - Indrajeet Singh

0

最简单的方法是将第一个列表（不要称其为input！）转换为字符串（尖括号将多位数“组合”在一起）：

input_str = "".join("<"+str(i)+">" for i in input_list)

将第二个列表转换为正则表达式，允许在必需项之间添加可选的附加项：

lookup_str = ".*" + ".+".join("<"+str(i)+">" for i in lookup_list) + ".+"

现在，检查输入字符串是否与正则表达式匹配：

if (re.search(lookup_str, input_str)): # there is a match

- DYZ

好主意，所以模式不需要括号，就像"[.+]".join一样？ - RichieV

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- alani · Accepted Answer

您可以使用迭代器遍历输入列表。使用next方法获取每个值。如果在迭代完所有元素之前没有找到匹配项，则会得到一个StopIteration，此时应返回False。

def check(input_, lookup_list):
    it = iter(input_)
    try:
        for i in lookup_list:
            # read values from the input list until we find one which 
            # matches the current value from the lookup list
            while next(it) != i: 
                pass
        # we found matches for everything on the lookup list
        return True
    except StopIteration:
        # we tried to go past the end of the input list
        return False