python 3

from collections import Iterable

L = [[[1, 2, 3], [4, 5]], 6,[7,[8,9,[10]]]]

def flatten(thing):
    result = []

    if isinstance(thing, Iterable):
        for item in thing:
            result.extend(flatten(item))
    else:
        result.append(thing)

    return result


flat = flatten(L)
print(flat)

这个版本的flatten避免了python的递归限制(因此可以处理任意深度的嵌套迭代对象)。它是一个生成器，可以处理字符串和任意可迭代对象(甚至是无限迭代对象)。

import itertools as IT
import collections

def flatten(iterable, ltypes=collections.Iterable):
    remainder = iter(iterable)
    while True:
        first = next(remainder)
        if isinstance(first, ltypes) and not isinstance(first, (str, bytes)):
            remainder = IT.chain(first, remainder)
        else:
            yield first

下面是一些演示它用法的例子:

print(list(IT.islice(flatten(IT.repeat(1)),10)))
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3),
                                       {10,20,30},
                                       'foo bar'.split(),
                                       IT.repeat(1),)),10)))
# [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1]

print(list(flatten([[1,2,[3,4]]])))
# [1, 2, 3, 4]

seq = ([[chr(i),chr(i-32)] for i in range(ord('a'), ord('z')+1)] + list(range(0,9)))
print(list(flatten(seq)))
# ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H',
# 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P',
# 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X',
# 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8]

虽然flatten可以处理无限的生成器，但它不能处理无限的嵌套:

def infinitely_nested():
    while True:
        yield IT.chain(infinitely_nested(), IT.repeat(1))

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs

尝试在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
>>>

@unutbu的非递归解决方案的生成器版本，由@Andrew在评论中要求:

def genflat(l, ltypes=collections.Sequence):
    l = list(l)
    i = 0
    while i < len(l):
        while isinstance(l[i], ltypes):
            if not l[i]:
                l.pop(i)
                i -= 1
                break
            else:
                l[i:i + 1] = l[i]
        yield l[i]
        i += 1

这个生成器的简化版本:

def genflat(l, ltypes=collections.Sequence):
    l = list(l)
    while l:
        while l and isinstance(l[0], ltypes):
            l[0:1] = l[0]
        if l: yield l.pop(0)

这是另一种py2方法，我不确定它是否最快或最优雅或最安全…

from collections import Iterable
from itertools import imap, repeat, chain


def flat(seqs, ignore=(int, long, float, basestring)):
    return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

它可以忽略你想要的任何特定(或派生)类型，它返回一个迭代器，所以你可以将它转换为任何特定的容器，如list, tuple, dict或简单地消耗它，以减少内存占用，无论是好是坏，它可以处理初始的不可迭代对象，如int…

注意，大部分繁重的工作都是在C中完成的，因为据我所知，itertools就是这样实现的，所以虽然它是递归的，但AFAIK它不受python递归深度的限制，因为函数调用是在C中发生的，尽管这并不意味着你受到内存的限制，特别是在OS X中，它的堆栈大小有一个硬限制，直到今天(OS X Mavericks)…

有一个稍微快一点的方法，但不太便携的方法，只有在你可以假设输入的基本元素可以显式确定的情况下才使用它，否则你会得到一个无限递归，而OS X有限的堆栈大小，将抛出一个分割错误相当快……

def flat(seqs, ignore={int, long, float, str, unicode}):
    return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

这里我们使用集合来检查类型，所以它使用O(1) vs O(类型数量)来检查是否应该忽略一个元素，当然，任何带有指定的被忽略类型的派生类型的值都会失败，这就是为什么它使用str, unicode，所以要小心使用它…

测试:

import random

def test_flat(test_size=2000):
    def increase_depth(value, depth=1):
        for func in xrange(depth):
            value = repeat(value, 1)
        return value

    def random_sub_chaining(nested_values):
        for values in nested_values:
            yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10)))))

    expected_values = zip(xrange(test_size), imap(str, xrange(test_size)))
    nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values)))
    assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),)))))

>>> test_flat()
>>> list(flat([[[1, 2, 3], [4, 5]], 6]))
[1, 2, 3, 4, 5, 6]
>>>  

$ uname -a
Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun  3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64
$ python --version
Python 2.7.5

在尝试回答这样一个问题时，您确实需要给出作为解决方案的代码的局限性。如果它只是关于性能，我不会太介意，但作为解决方案提出的大多数代码(包括公认的答案)都不能平坦任何深度大于1000的列表。

当我说大多数代码时，我指的是所有使用任何形式递归的代码(或调用递归的标准库函数)。所有这些代码都失败了，因为每次递归调用，(调用)堆栈都会增加一个单元，(默认)python调用堆栈的大小为1000。

如果您对调用堆栈不太熟悉，那么下面的内容可能会有所帮助(否则您可以直接滚动到Implementation)。

调用堆栈大小和递归编程(地下城类比)

找到宝藏和出口

想象一下，你进入一个有编号房间的巨大地牢，寻找宝藏。你不知道那个地方，但你对如何找到宝藏有一些暗示。每个指示都是一个谜(难度不同，但你无法预测它们有多难)。你决定考虑一个节省时间的策略，你做了两个观察:

找到宝藏很难(很长时间)，因为你必须解决(可能很难的)谜语才能到达那里。 一旦找到宝藏，回到入口可能很容易，你只需要在另一个方向使用相同的路径(尽管这需要一点记忆来回忆你的路径)。

当你进入地下城时，你会注意到这里有一个小笔记本。你决定用它来写下你在解开谜语后(当进入一个新房间时)离开的每个房间，这样你就可以回到入口。这是一个天才的想法，你甚至不会花一分钱来实施你的策略。

你进入地下城，成功地解决了前1001个谜语，但你没有计划的事情出现了，你借来的笔记本没有空间了。你决定放弃你的任务，因为你宁愿没有宝藏也不愿永远迷失在地牢里(这看起来确实很聪明)。

执行递归程序

基本上，这和找到宝藏是一样的。地牢是计算机的内存，你现在的目标不是找到宝藏，而是计算某个函数(为给定的x找到f(x))。指示只是帮助你求解f(x)的子例程。你的策略与调用堆栈策略相同，notebook是堆栈，rooms是函数的返回地址:

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

The problem you encountered in the dungeon will be the same here, the call stack has a finite size (here 1000) and therefore, if you enter too many functions without returning back then you'll fill the call stack and have an error that look like "Dear adventurer, I'm very sorry but your notebook is full": RecursionError: maximum recursion depth exceeded. Note that you don't need recursion to fill the call stack, but it's very unlikely that a non-recursive program call 1000 functions without ever returning. It's important to also understand that once you returned from a function, the call stack is freed from the address used (hence the name "stack", return address are pushed in before entering a function and pulled out when returning). In the special case of a simple recursion (a function f that call itself once -- over and over --) you will enter f over and over until the computation is finished (until the treasure is found) and return from f until you go back to the place where you called f in the first place. The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other.

如何避免这个问题?

这其实很简单:“如果你不知道递归有多深，就不要使用递归”。这并不总是正确的，因为在某些情况下，尾部调用递归可以被优化(TCO)。但在python中，情况并非如此，即使“写得很好”的递归函数也不会优化堆栈的使用。Guido有一篇关于这个问题的有趣文章:尾递归消除。

有一种技术可以让任何递归函数迭代，这种技术我们可以叫它，带上你自己的笔记本。例如，在我们的特定情况下，我们只是在探索一个列表，进入一个房间相当于进入一个子列表，你应该问自己的问题是，我如何从一个列表返回到它的父列表?答案并不复杂，重复以下步骤直到栈空:

当输入新的子列表时，将当前列表地址和索引推入堆栈(注意，列表地址+索引也是一个地址，因此我们只是使用与调用堆栈使用的完全相同的技术); 每次找到一个项目，交出它(或将它们添加到列表中); 一旦一个列表被完全浏览，使用堆栈返回地址(和索引)返回到父列表。

还要注意，这等价于树中的DFS，其中有些节点是子列表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，您还“需要”一个堆栈。我之前提出的实现会产生以下状态(对于堆栈和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中，你可以通过使用迭代器而不是简单的列表来简化实现。对(sub)迭代器的引用将用于存储子列表的返回地址(而不是同时拥有列表地址和索引)。这不是很大的区别，但我觉得这样更有可读性(也更快一点):

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

这将字符串视为“简单项”，因此平坦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]]]]]。