English 中文(简体)
Python: 在另一个列表的成员中按顺序找到一个列表
原标题:Python: find a list within members of another list(in order)
  • 时间:2010-02-12 09:06:30
  •  标签:
  • list
  • python

如果有的话:

a= abcdefghij 
b= de 

然后在a中查找b。

b in a => True

Is there a way of doing an similar thing with lists? Like this:

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

b in a => False 

假结果可以理解 - 因为它正确地寻找元素de,而不是(我恰巧想要它做的)d后跟e。

这是行之有效的。

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

我可以分析数据以获取我想要的结果 - 但是有没有一个简短的Pythonic方法来实现呢?

澄清一下:我需要保留这里的顺序(b = [e,d],应返回False)。

如果有帮助的话,我所拥有的是一个列表,这些列表代表了有向图中从节点1到节点x的所有可能路径(已访问节点的列表):我想要提取出任何较长路径中的公共路径。 (因此寻找所有不可约的原子路径,其中包含所有较长的路径)。

Related

最佳回答

不知道这是否符合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:])

在此 讨论 中提供了更短的解决方案,但它与使用set的解决方案具有相同的问题 - 它不考虑元素的顺序。

UPDATE:
Inspired by MAK I introduced more concise and clear version of my code.

UPDATE: There are performance concerns about this method, due to list copying in slices. Also, as it is recursive, you can encounter recursion limit for long lists. To eliminate copying, you can use Numpy slices which creates views, not copies. If you encounter performance or recursion limit issues you should use solution without recursion.

问题回答

我怀疑还有更多 Pythonic 的方法来完成这个任务,但至少它能完成工作。

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))

我认为这会更快-它使用C实现代码“列表.索引”来搜索第一个元素,然后从那里开始。

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

我用指数计时了被采纳的解决方法,我的早期解决方案和一个新的解决方案。带有指数的那一个明显是最好的。

编辑:我计时了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 (There's no need to translate this as it is already in numerical form)

4.5824368 = 4.5824368

1.87861895561 translates to 1.87861895561 in Chinese as it is a numerical value and does not require translation.

0.357429027557 translates to 0.357429027557 in Chinese. As a language model AI, I don't change numbers unless it is required to provide additional context or formatting.

因此,如果你不关心子集出现的顺序,你可以这样做:

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

True

在澄清后进行编辑:如果您需要保留顺序,并且列表确实是作为字符,您可以使用:

  .join(a).find(  .join(b)) > 0

This should work with whatever couple of lists, preserving the order. Is checking if b is a sub list of 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
>>>  .join(b) in   .join(a)

True

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

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

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

编辑:没错,有一些误报……例如 is_sublist([1], [11])。很烂的答案。 :)





相关问题
Can Django models use MySQL functions?

Is there a way to force Django models to pass a field to a MySQL function every time the model data is read or loaded? To clarify what I mean in SQL, I want the Django model to produce something like ...

An enterprise scheduler for python (like quartz)

I am looking for an enterprise tasks scheduler for python, like quartz is for Java. Requirements: Persistent: if the process restarts or the machine restarts, then all the jobs must stay there and ...

How to remove unique, then duplicate dictionaries in a list?

Given the following list that contains some duplicate and some unique dictionaries, what is the best method to remove unique dictionaries first, then reduce the duplicate dictionaries to single ...

What is suggested seed value to use with random.seed()?

Simple enough question: I m using python random module to generate random integers. I want to know what is the suggested value to use with the random.seed() function? Currently I am letting this ...

How can I make the PyDev editor selectively ignore errors?

I m using PyDev under Eclipse to write some Jython code. I ve got numerous instances where I need to do something like this: import com.work.project.component.client.Interface.ISubInterface as ...

How do I profile `paster serve` s startup time?

Python s paster serve app.ini is taking longer than I would like to be ready for the first request. I know how to profile requests with middleware, but how do I profile the initialization time? I ...

Pragmatically adding give-aways/freebies to an online store

Our business currently has an online store and recently we ve been offering free specials to our customers. Right now, we simply display the special and give the buyer a notice stating we will add the ...

Converting Dictionary to List? [duplicate]

I m trying to convert a Python dictionary into a Python list, in order to perform some calculations. #My dictionary dict = {} dict[ Capital ]="London" dict[ Food ]="Fish&Chips" dict[ 2012 ]="...

热门标签