python - 如何深度搜索 Python 列表？

Question

我想在 Python 中的列表中进行深度搜索。例如，我想知道 5 是否在my_list。

my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]

我怎样才能做到这一点？

Answer 1

不确定使用多级嵌套的快速方法，但是像这样的递归算法可以解决问题：

def nestedSearch(nested, v):
    for element in nested:
        if isinstance(element, list):
            if nestedSearch(element, v):
                return True
        elif element == v:
            return True
    return False

你也可以看看这个扁平化多嵌套列表：

用于展平嵌套列表的递归生成器

Answer 2

您可以将该flatten函数（将其视为 的递归版本itertools.chain）与 Python 的标准in运算符（在生成器上进行线性搜索）结合起来得到：

>>> def flatten(nested):
    try:
        for sublist in nested:
            for element in flatten(sublist):
                yield element
    except TypeError:
        yield nested


>>> my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]
>>> 5 in flatten(my_list)
True

根据链接问题中的评论，如果您要搜索的内容是可迭代的，您将需要优化flatten代码 - 例如，元组将像列表一样被展平到搜索中，并且搜索字符串会递归，直到它达到 Python 的堆栈限制。

Answer 3

如果您有列表列表，则可以使用此方法

>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> [item for sublist in l for item in sublist]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 5 in [item for sublist in l for item in sublist]
True

首先使用 O(n) 展平列表并通过它进行搜索。

如果您的列表看起来像在您的示例中，我想不出比使用 for-loops 的另一种方法......

Answer 4

一种方法：

def deapSearch(searchElement, searchList):
    for element in searchList:
        if element == searchElement:
            return True
        elif type(element) == type(list):
            found = deapSearch(searchElement, element)
            if found:
                return found
    return False
deapSearch(5, my_list)
True
deapSearch(4, my_list)
True

不漂亮但工作。

Answer 5

我最近需要这样做并且需要一个简单的解决方案。所以我将它添加为一种快速而肮脏的方式来展平/搜索列表（可能不是一个完美的解决方案，但它对我有用）。

>>> my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]
>>> str(5) in str(my_list) # returns True
>>> str(my_list).find(str(5)) # returns the index

编辑：也添加一个正则表达式解决方案。但是如果你有更复杂的情况，那么你不妨遍历列表。

>>> import re
>>> str(5) in re.findall('(?<=[,\[])([ a-zA-Z0-9 ]+)(?=[,\]])', str(my_list))

正则表达式本质上是扁平化列表，但不适用于列表项中的特殊字符。

Answer 6

如果您只有一个带有整数或字符的嵌套列表，解决此问题的一种方法是创建一个没有所有不需要的元素的列表（没有 '[' ， ']' ...）：

假设我们有一个带有 chars 的嵌套列表：

>>> nested = [[[[['F', 'B'], 'G'], ['D', 'A']], 'C'], 'E']
>>> string = str(nested)
>>> string = string.replace('[','',len(string))
>>> string = string.replace(']','',len(string))
>>> string = string.replace("'","",len(string))
>>> string = string.replace(" ","",len(string))
>>> string = string.split(',')

它给 ：

>>> print (string)
['F', 'B', 'G', 'D', 'A', 'C', 'E']

现在您可以轻松搜索而无需任何循环：

>>> 'F' in string
True