将一个不规则（任意嵌套）的列表展开为一维列表

尝试在Python中创建一个能够展平不规则列表的函数是很有趣的事情，但当然这也是Python的目的（让编程变得有趣）。以下生成器可以很好地工作，但有一些注意事项：

def flatten(iterable):
    try:
        for item in iterable:
            yield from flatten(item)
    except TypeError:
        yield iterable

这段代码将压缩一些数据类型，但是可能会忽略掉一些本应该保留的数据类型（比如 bytearray、bytes 和 str 对象）。此外，代码中还使用了一个前提条件：从一个不可迭代的对象请求迭代器会引发 TypeError 异常。

>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> def flatten(iterable):
    try:
        for item in iterable:
            yield from flatten(item)
    except TypeError:
        yield iterable


>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>>

---

编辑：

我不同意之前的实现。问题在于你不能将不可迭代的东西展开。这会让人感到困惑，并给参数留下错误的印象。

>>> list(flatten(123))
[123]
>>>

下面的生成器与第一个生成器几乎相同，但不会出现尝试展开非可迭代对象的问题。当给它不适当的参数时就会像我们预期的那样失败。

def flatten(iterable):
    for item in iterable:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

测试生成器与提供的列表一起使用正常工作。然而，如果将非可迭代对象传递给它，新代码将引发TypeError。下面展示了新行为的示例。

>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>> list(flatten(123))
Traceback (most recent call last):
  File "<pyshell#32>", line 1, in <module>
    list(flatten(123))
  File "<pyshell#27>", line 2, in flatten
    for item in iterable:
TypeError: 'int' object is not iterable
>>>

当尝试回答这样的问题时，你真的需要给出你提出的代码解决方案的限制。如果只是关于性能，我不会太在意，但大多数提出的代码解决方案（包括被接受的答案）都无法展开任何深度大于1000的列表。
当我说“大多数代码”时，我指的是使用任何形式的递归（或调用递归的标准库函数）的所有代码。所有这些代码都失败了，因为对于每个递归调用，（调用）堆栈增加一单位，而（默认）Python调用堆栈的大小为1000。
如果您对调用堆栈不太熟悉，那么也许以下内容可以帮助您（否则您可以直接滚动到“实现”部分）。
调用堆栈大小和递归编程（地牢类比）
找到宝藏和出口
想象一下，您进入了一个有编号房间的巨大地牢，寻找宝藏。您不知道这个地方，但您有一些寻找宝藏的指示。每个指示都是一个谜语（难度各异，但您无法预测它们的难度）。您决定考虑一下节省时间的策略，您做出了两个观察：
1.找到宝藏很难（长时间），因为您必须解决（可能很难的）谜题才能到达那里。
2.一旦找到宝藏，返回入口可能很容易，您只需要沿着相同的路径向另一个方向走（尽管这需要一些记忆来回忆您的路径）。
当进入地牢时，您注意到这里有一个小笔记本。您决定使用它来记录每次解决谜题后退出的房间（进入新房间时），这样您就可以返回入口了。这是一个天才的想法，您甚至不需要花一分钱来实现您的策略。
您进入地牢，成功解决了前1001个谜题，但接下来出现了您没有计划过的事情，您借来的笔记本没有空间了。您决定放弃您的探险，因为您宁愿没有宝藏也不想永远迷失在地牢中（这看起来确实很聪明）。
执行递归程序
基本上，这与找到宝藏完全相同。地牢是计算机内存，您现在的目标不是找到宝藏，而是计算某个函数（为给定的x找到f（x））。指示只是帮助您解决f（x）的子例程。您的策略与调用堆栈策略相同，笔记本是堆栈，房间是函数的返回地址：

x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected 
print(' '.join(y))

在这里遇到的问题和在地牢中遇到的问题相同，调用栈有一个有限的大小（这里是1000），因此，如果进入太多函数而没有返回，则会填满调用栈，并出现以下类似的错误：“亲爱的冒险家，非常抱歉，您的笔记本已经满了”：RecursionError：超过最大递归深度。请注意，您不需要使用递归来填充调用栈，但是一个非递归程序调用1000个函数而从未返回极其不可能。还要重要的是一旦你从一个函数返回，调用栈就会从使用的地址中释放（因此称为“堆栈”，在进入函数之前将返回地址推入堆栈中，在返回时将其弹出）。在简单递归的特殊情况下（一个调用自身一次 - 一次又一次 - 的函数f），您将一次又一次地进入f，直到计算完成（直到找到宝藏）并从f返回，直到返回到第一次调用f的地方。在结束处，调用栈将从所有返回地址中依次释放。

如何避免出现此问题？

其实很简单：“如果您不知道递归可以走多深，请不要使用递归”。这并非总是正确的，因为在某些情况下，Tail Call递归可以被优化（TCO）。但是在Python中，情况并非如此，即使是“良好编写”的递归函数也不会优化堆栈使用。Guido在这个问题上有一篇有趣的文章：Tail Recursion Elimination。

有一种技术可以将任何递归函数转换为迭代函数，这种技术我们可以称之为自带笔记本。例如，在我们的特定情况中，我们只是在探索列表，进入一个房间等同于进入一个子列表，您应该问自己的问题是：我如何从一个列表返回其父列表？答案并不复杂，只需重复以下步骤，直到stack为空：

1. 当进入新的子列表时（请注意，列表地址+索引也是一个地址，因此我们只使用调用堆栈使用的完全相同的技术），在stack中推入当前列表的地址和索引；
2. 每次发现一个项时，yield它（或将它们添加到列表中）；
3. 一旦完全探索了列表，请使用stack 返回address（和index）回到父列表。

请注意，这相当于在一棵树中进行深度优先搜索，其中一些节点是子列表A = [1, 2]，而另一些节点是简单项：0, 1, 2, 3, 4（对于L = [0, [1,2], 3, 4]）。该树看起来像这样：

                    L
                    |
           -------------------
           |     |     |     |
           0   --A--   3     4
               |   |
               1   2

DFS遍历的先序顺序为：L、0、A、1、2、3、4。请记住，要实现迭代DFS，还需要一个栈。我之前提出的实现方式会导致以下状态（对于“stack”和“flat_list”）：

init.:  stack=[(L, 0)]
**0**:  stack=[(L, 0)],         flat_list=[0]
**A**:  stack=[(L, 1), (A, 0)], flat_list=[0]
**1**:  stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**:  stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**:  stack=[(L, 2)],         flat_list=[0, 1, 2, 3]
**3**:  stack=[(L, 3)],         flat_list=[0, 1, 2, 3, 4]
return: stack=[],               flat_list=[0, 1, 2, 3, 4]

在这个例子中，栈的最大大小为2，因为输入列表（因此树）的深度为2。

实现

对于实现，在Python中，您可以通过使用迭代器而不是简单列表来简化一些内容。对（子）迭代器的引用将用于存储子列表返回地址（而不是同时具有列表地址和索引）。虽然这并没有太大的区别，但我觉得这更易读（也更快一些）：

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

此外，请注意在 is_list_like 中，我使用了 isinstance(item, list)，它可以修改以处理更多的输入类型，但这里我只想要一个最简单的版本，其中 (iterable) 只是一个列表。但您也可以这样做：

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

这将字符串视为“简单项”，因此flatten_iter([["test", "a"], "b])将返回["test", "a", "b"]，而不是["t", "e", "s", "t", "a", "b"]。请注意，在这种情况下，每个项上都会调用两次iter(item)，假装这是一个让读者更清晰的练习。

测试和其他实现备注

最后，请记住，您无法使用print(L)打印无限嵌套的列表L，因为内部将使用递归调用__repr__（RecursionError：在获取对象的repr时超过了最大递归深度）。出于同样的原因，涉及str的flatten解决方案将以相同的错误消息失败。

如果需要测试您的解决方案，可以使用此函数生成简单的嵌套列表：

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

这将得到：build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]]。

这是一个简单的函数，可以将任意深度的列表扁平化。 为了避免栈溢出，不使用递归。

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]

    """
    nested_list = deepcopy(nested_list)

    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

虽然已经有一种优雅且非常符合Python风格的答案被选中了，但我想呈现我的解决方案供评审：

def flat(l):
    ret = []
    for i in l:
        if isinstance(i, list) or isinstance(i, tuple):
            ret.extend(flat(i))
        else:
            ret.append(i)
    return ret

请告诉我这段代码好坏如何？

我更喜欢简单的答案。不使用生成器，不使用递归或递归深度限制，而是采用迭代：

def flatten(TheList):
    listIsNested = True

    while listIsNested:                 #outer loop
        keepChecking = False
        Temp = []

        for element in TheList:         #inner loop
            if isinstance(element,list):
                Temp.extend(element)
                keepChecking = True
            else:
                Temp.append(element)

        listIsNested = keepChecking     #determine if outer loop exits
        TheList = Temp[:]

    return TheList

这个方法需要两个列表：一个内部的for循环和一个外部的while循环。

内部的for循环遍历列表。如果它发现一个列表元素，它（1）使用list.extend()将其扁平化一级，并（2）将keepChecking切换为True。keepchecking用于控制外部while循环。如果外部循环被设置为true，则触发内部循环进行另一次遍历。

这些遍历会一直持续，直到找不到更多嵌套的列表。当最后一次遍历中没有发现嵌套列表时，keepChecking永远不会被置为true，这意味着listIsNested保持为false，外部while循环退出。

然后返回扁平化的列表。

测试运行

flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

我没有浏览所有已有的答案，但是这里有一行代码，借鉴了Lisp的方式来处理列表的首尾。

def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l]

这里有一个简单的案例和一个不那么简单的案例 -

>>> flatten([1,[2,3],4])
[1, 2, 3, 4]

>>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30])
[1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
>>> 

只需使用 funcy 库: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list

我不确定这是否更快或更有效，但这是我的做法：

def flatten(lst):
    return eval('[' + str(lst).replace('[', '').replace(']', '') + ']')

L = [[[1, 2, 3], [4, 5]], 6]
print(flatten(L))

这里的flatten函数将列表转换为字符串，去除所有方括号，再将方括号重新附加到两端，然后将其转换回列表。
不过，如果你知道在字符串中的列表中有方括号，比如[[1, 2], "[3, 4] and [5]"]，那么你需要采取其他方法。

我知道已经有很多非常好的答案了，但我想添加一个使用函数式编程方法解决问题的答案。在这个答案中，我使用了双重递归：

def flatten_list(seq):
    if not seq:
        return []
    elif isinstance(seq[0],list):
        return (flatten_list(seq[0])+flatten_list(seq[1:]))
    else:
        return [seq[0]]+flatten_list(seq[1:])

print(flatten_list([1,2,[3,[4],5],[6,7]]))

输出：

[1, 2, 3, 4, 5, 6, 7]

我很惊讶没有人想到这个。该死的递归，我不理解这里高级人士所做的递归答案。无论如何，这是我对此的尝试。但需要注意的是，它非常特定于原始问题的用例。

import re

L = [[[1, 2, 3], [4, 5]], 6]
flattened_list = re.sub("[\[\]]", "", str(L)).replace(" ", "").split(",")
new_list = list(map(int, flattened_list))
print(new_list)

输出：

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