Python:在另一个列表的成员中查找列表(按顺序)

hts6caw3  于 2022-12-10  发布在  Python
关注(0)|答案(9)|浏览(167)

如果我有这个:

a='abcdefghij'
b='de'

然后在a中找到B:

b in a => True

有没有类似的方法来处理列表?比如:

a=list('abcdefghij')
b=list('de')

b in a => False

“False”的结果是可以理解的-因为它正确地寻找一个元素“de”,而不是(我碰巧希望它这样做)“d”后面跟着“e”
这是作品,我知道:

a=['a', 'b', 'c', ['d', 'e'], 'f', 'g', 'h']
b=list('de')
b in a => True

我可以通过处理数据来得到我想要的东西--但是有没有一种简短的Python方法来做到这一点呢?
澄清一下:我需要保留这里的顺序(B=['e','d'],应该返回False)。
如果有帮助的话,我有一个清单:这些列表表示有向图中从节点1到节点X的所有可能路径(被访问节点的列表):我想在任何较长的路径中“分解”出公共路径。(所以寻找所有组成所有较长路径的不可约的“原子”路径)。

相关

gr8qqesn

gr8qqesn1#

我怀疑还有更多的Python式的方法来做这件事,但至少它完成了工作:

l=list('abcdefgh')
pat=list('de')

print pat in l # Returns False
print any(l[i:i+len(pat)]==pat for i in xrange(len(l)-len(pat)+1))
vwhgwdsa

vwhgwdsa2#

不知道这是不是很Python,但我会这样做:

def is_sublist(a, b):
    if not a: return True
    if not b: return False
    return b[:len(a)] == a or is_sublist(a, b[1:])

discussion中提供了更短的解决方案,但它遇到了与set解决方案相同的问题-它不考虑元素的顺序。
最新消息:
受MAK的启发,我引入了更简洁明了的代码版本。
UPDATE:由于在切片中复制列表,因此此方法存在性能问题。此外,由于它是递归的,因此可能会遇到长列表的递归限制。若要消除复制,可以使用Numpy切片(creates views, not copies)。如果遇到性能或递归限制问题,则应使用不带递归的解决方案。

nbysray5

nbysray53#

我认为这会更快-它使用C实现list.index来搜索第一个元素,然后从那里开始。

def find_sublist(sub, bigger):
    if not bigger:
        return -1
    if not sub:
        return 0
    first, rest = sub[0], sub[1:]
    pos = 0
    try:
        while True:
            pos = bigger.index(first, pos) + 1
            if not rest or bigger[pos:pos+len(rest)] == rest:
                return pos
    except ValueError:
        return -1

data = list('abcdfghdesdkflksdkeeddefaksda')
print find_sublist(list('def'), data)

请注意,它返回的是子列表在列表中的位置,而不仅仅是TrueFalse。如果只需要bool,可以使用以下语句:

def is_sublist(sub, bigger): 
    return find_sublist(sub, bigger) >= 0
mlnl4t2r

mlnl4t2r4#

我对已接受的解决方案、我之前的解决方案和一个有索引的新解决方案进行了计时。有索引的解决方案显然是最好的。
编辑:我计算了Nosklo的解决方案,它甚至比我想出来的要好得多。:)

def is_sublist_index(a, b):
    if not a:
        return True

    index = 0
    for elem in b:
        if elem == a[index]:
            index += 1
            if index == len(a):
                return True
        elif elem == a[0]:
            index = 1
        else:
            index = 0

    return False

def is_sublist(a, b):
    return str(a)[1:-1] in str(b)[1:-1]

def is_sublist_copylist(a, b):
    if a == []: return True
    if b == []: return False
    return b[:len(a)] == a or is_sublist_copylist(a, b[1:])

from timeit import Timer
print Timer('is_sublist([99999], range(100000))', setup='from __main__ import is_sublist').timeit(number=100)
print Timer('is_sublist_copylist([99999], range(100000))', setup='from __main__ import is_sublist_copylist').timeit(number=100)
print Timer('is_sublist_index([99999], range(100000))', setup='from __main__ import is_sublist_index').timeit(number=100)
print Timer('sublist_nosklo([99999], range(100000))', setup='from __main__ import sublist_nosklo').timeit(number=100)

以秒为单位的输出:
4.51677298546
4.5824368
1.87861895561
0.357429027557

ddarikpa

ddarikpa5#

因此,如果您不关心子集的显示顺序,则可以执行以下操作:

a=list('abcdefghij')
b=list('de')
set(b).issubset(set(a))

True

澄清后进行编辑:如果你需要保持顺序,并且列表中确实是你问题中的字符,你可以用途:

''.join(a).find(''.join(b)) > 0
8fsztsew

8fsztsew6#

这应该适用于任何一对列表,并保持顺序。检查 B 是否是 a 的子列表

def is_sublist(b,a): 

    if len(b) > len(a):
        return False    

    if a == b:
        return True    

    i = 0
    while i <= len(a) - len(b):
        if a[i] == b[0]:
            flag = True
            j = 1
            while i+j < len(a) and j < len(b):
                if a[i+j] != b[j]:
                    flag = False
                j += 1
            if flag:
                return True
        i += 1
    return False
w80xi6nr

w80xi6nr7#

>>>''.join(b) in ''.join(a)

True
5hcedyr0

5hcedyr08#

不确定您的应用程序有多复杂,但对于列表中的模式匹配,pyparsing非常智能和易于使用。

vsmadaxz

vsmadaxz9#

使用列表的字符串表示并删除方括号。:)

def is_sublist(a, b):
    return str(a)[1:-1] in str(b)

编辑:对,有误报... eidogg. is_sublist([1], [11]) .蹩脚的答案。:)

相关问题