是的，我知道这个主题之前已经被讨论过了:
Python成语链(扁平化)有限迭代对象的无限迭代? 在Python中扁平化一个浅列表 理解平展一个序列的序列吗? 我如何从列表的列表中创建一个平面列表?
但据我所知，所有的解决方案，除了一个，在像[[[1,2,3]，[4,5]]，6]这样的列表上失败，其中期望的输出是[1,2,3,4,5,6](或者更好，一个迭代器)。
我看到的唯一解决方案，适用于任意嵌套是在这个问题:
def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result
这是最好的方法吗?我是不是忽略了什么?任何问题吗?
当前回答
这是python2上flatten的一个简单实现
flatten=lambda l: reduce(lambda x,y:x+y,map(flatten,l),[]) if isinstance(l,list) else [l]
test=[[1,2,3,[3,4,5],[6,7,[8,9,[10,[11,[12,13,14]]]]]],]
print flatten(test)
#output [1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
其他回答
这是一个简单的函数，它将任意深度的列表平展。不递归，避免堆栈溢出。
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
下面是2.7.5中的compiler.ast.flatten实现:
def flatten(seq):
l = []
for elt in seq:
t = type(elt)
if t is tuple or t is list:
for elt2 in flatten(elt):
l.append(elt2)
else:
l.append(elt)
return l
有更好、更快的方法(如果你已经到达这里，你已经看到它们了)
还要注意:
2.6版后已移除:在Python 3中已移除编译器包。
在尝试回答这样一个问题时，您确实需要给出作为解决方案的代码的局限性。如果它只是关于性能，我不会太介意，但作为解决方案提出的大多数代码(包括公认的答案)都不能平坦任何深度大于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]]]]]。
没有装饰。只有发冷。
recursive_list_of_lists = [1,2,3,[1,2,[[3,4,[5]],7,0,1,10],100,[101,[101,[[101]],2]],0]]
k = []
def flatten(subl):
for i in subl:
if type(i) != type([1]):
k.append(i)
else:
flatten(i)
flatten(recursive_list_of_lists)
print(k)
[1, 2, 3, 1, 2, 3, 4, 5, 7, 0, 1, 10, 100, 101, 101, 101, 2, 0]
不使用实例的简单函数
L = [[[1, 2, 3], [4, 5]], 6]
l1 = []
def FlattenList(List1):
for i in range(len(List1)):
if type(List1[i]) == type([]):
FlattenList(List1[i])
else:
l1.append(List1[i])
return l1
FlattenList(L)
[1, 2, 3, 4, 5, 6]
