将不规则的Python多维数组拉平到一维的方法实现

原始需求：

例如有一个列表：

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

希望把它转换成下面这种形式：

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

其实这个非常简单，我将分享三个一行式代码来解决这个问题。

但如果是下面这种不规则的多维列表：

l = [[1, 2], [3, 4], [5, [6, 7, [8, 9]]], 10, [11, [12, 13, [14, 15, [16]]]]]

我们想将它拉平到一维列表：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

又该怎么实现呢？

文末将演示通过递归或栈来实现深度优先遍历策略从而解决这个问题。

使用numpy拉平数组

import numpy as np
np.array(l).flatten().tolist()

结果：

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

使用python拉平数组

使用numpy数组拉平数组，其实很受限，一旦列表内部每个元素的长度不一致，numpy就不好使了：

l = [[1, 2, 3], [4, 5], [6, 7], [8, 9, 10, 11]]
np.array(l).flatten().tolist()

D:\Anaconda3\lib\site-packages\ipykernel_launcher.py:2: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray

结果：

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

这时我们可以通过python的itertools来实现高效的操作：

import itertools
list(itertools.chain(*l))

结果：

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

当然还有一种更高级的操作方法是直接使用sum函数：

sum(l, [])

结果：

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

你可能一脸懵逼，为什么sum函数可以实现列表的拉平？下面我翻译一下，这段代码实际做了什么：

result = []
for i in l:
  result += i
result

结果：

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

将不规则多维数组拉平到1维

例如，对于下面这个复杂的列表：

l = [[1, 2], [3, 4], [5, [6, 7, [8, 9]]], 10, [11, [12, 13, [14, 15, [16]]]]]
l

结果：

[[1, 2], [3, 4], [5, [6, 7, [8, 9]]], 10, [11, [12, 13, [14, 15, [16]]]]]

这样的列表，对于上面的方法来说已经都不好使了，这个时候怎么办呢？

当然对于这种长度不长的列表，我们可以玩点小技巧：

list_str = str(l).replace("[", "").replace("]", "")
eval(f"[{list_str}]")

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

当然，使用正则替换更佳：

import re
eval(re.sub("(?!^)\[|\](?!$)", "", str(l)))

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

原理就是先将这个列表转成普通的字符串，再将所有的[]字符都去掉，再转成单维列表的字符串形式之后，用eval函数进行解析。但这种方式在列表足够长的时候显然是不合适的，会出现效率低下的问题。

深度优先遍历策略拉平多维数组

下面我介绍一个正常的解决这个问题的办法，那就是使用深度优先遍历策略来解决这个问题，当然如果你对拉平的结果没有顺序的要求还可以使用广度优先遍历的策略。

深度优先遍历策略，最简单直接的思路是使用递归来实现：

def flatten(items, result=[]):
  for item in items:
    if isinstance(item, list):
      flatten(item, result)
    else:
      result.append(item)


result = []
flatten(l, result)
result

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

虽然递归可能出现调用栈过多导致性能下降或程序挂掉，但Python可以借助生成器让递归调用变成普通调用：

def flatten(items):
  for item in items:
    if isinstance(item, list):
      yield from flatten(item)
    else:
      yield item


result = [e for e in flatten(l)]
result

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

而如果我们想不使用递归或生成器类递归，可以直接借助一个栈来实现。

为了保证结果是原有的顺序，我们把左端作为栈顶，而数组不适合删除左端的数据，所以可以使用deque来作为栈。

首先，我们需要将原列表转换为deque，下面是处理代码：

from collections import deque

stack = deque(l)
result = []
while len(stack) != 0:
  item = stack.popleft()
  if isinstance(item, list):
    for e in reversed(item):
      stack.appendleft(e)
  else:
    result.append(item)
result

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

如果我们将原列表作为一个右端为栈顶的栈，可以通过向结果左端插入数据来保持原有的顺序：

from collections import deque

stack = l.copy()
result = deque()
while len(stack) != 0:
  item = stack.pop()
  if isinstance(item, list):
    for e in item:
      stack.append(e)
  else:
    result.appendleft(item)
result = list(result)
result

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

小结

想不到小小的列表拉平还有这么多学问，希望今天的分享能够对让你学有所获。