英文好像更容易懂:Flatten a nested list.

背景

女票初学Python,今天突然问我正如这篇文章题目的问题,作为老鸟的我当然分分钟撸了个递归版本甩过去,女票表示真是太简单明了了。但...女票说递归好难想到,可不可以用循环做到,然后我说没问题,分分钟就撸出来...然后发现好像用循环不太容易实现...

所以就有了这篇文章啦,其实找到循环处理的切入点了接来下就很容易了。

问题描述

对于一个多重嵌套的list,如:

a = ['this', 'is', ['a', ['sample', 'of', ['nested', 'lists'], ','],
                    'enjoy', ['it', 'and'], 'have'], 'fun']

如何将其中的嵌套去除,变成一个普通的list?如:

a = ['this', 'is', 'a', 'sample', 'of', 'nested', 'lists', ',',
     'enjoy', 'it', 'and', 'have', 'fun']

解决方法

递归

递归是最容易想到的了,遍历list,如果元素是list则递归,否则加入到新的list中,这样递归完成后得到的新的list就是“压平”后的list了。

def flat_list_rec(the_list, res=None):
    if res is None:
        res = []
    for item in the_list:
        if isinstance(item, list):
            flat_list_rec(item, res)
        else:
            res.append(item)
    return res

运行:

# before
a = ['this', 'is', ['a', ['sample', 'of', ['nested', 'lists'], ','],
                    'enjoy', ['it', 'and'], 'have'], 'fun']
# after
a = ['this', 'is', 'a', 'sample', 'of', 'nested', 'lists', ',',
     'enjoy', 'it', 'and', 'have', 'fun']

循环

递归虽然简单清晰,但毕竟需要递归栈,占用资源多且效率低,不妨考虑用循环解决。

Version 1

对list进行多次遍历,直到list不再有嵌套list为止。

即每次遍历都生成一个新的list,遍历时发现元素是list,则将此list中每个元素都加入到新的list中,而不管元素是不是仍然是list;如果某次遍历不再有元素是list,则停止遍历,此时得到的新list即“压平”后的list。

def flat_list_v_1(the_list):
    is_nested = True
    before = the_list[:]
    while is_nested:
        is_nested = False
        now = []
        for item in before:
            if isinstance(item, list):
                now.extend(item)
                is_nested = True
            else:
                now.append(item)
        before = now
    return before

运行:

# before
a = ['this', 'is', ['a', ['sample', 'of', ['nested', 'lists'], ','],
                    'enjoy', ['it', 'and'], 'have'], 'fun']
# after
a = ['this', 'is', 'a', 'sample', 'of', 'nested', 'lists', ',',
     'enjoy', 'it', 'and', 'have', 'fun']

Version 1缺陷很明显,遍历次数即list的嵌套深度,且每次遍历都会访问所有非list元素。

Version 2

Version 1 的两层循环实际上可以缩减成一层循环。对list遍历时,一旦碰到元素是list,则将此list的元素全都加入到原list的末尾,并将此list从原list中删除。简单来说就是每当碰到嵌套的list,就解开一层嵌套并添加到末尾,而遍历过的元素就一定能够保证不再有嵌套的list,这样遍历到末尾时就把原list“压平”了。

def flat_list_v_2(the_list):
    now = the_list[:]
    for item in now:
        if isinstance(item, list):
            now.extend(item)
            now.remove(item)
    return now

运行:

# before
a = ['this', 'is', ['a', ['sample', 'of', ['nested', 'lists'], ','],
                    'enjoy', ['it', 'and'], 'have'], 'fun']
# after
a = ['this', 'is', 'fun', 'a', 'enjoy', 'have', 'sample', 'of', ',',
     'it', 'and', 'nested', 'lists']

Version 2更简单,但会将原先的嵌套顺序打乱,可能不满足实际要求。

Version 3

为了解决Version 2中“压平”后顺序混乱的问题,可以考虑对Version 2进行改进。

Version 2是将嵌套的list解开一层嵌套后放到原list末尾,而实际上我们可以将list解开一层嵌套后直接放在原来的位置,即遍历到此元素发现是list,则解开此list,将其中的元素放到当前位置,再进行遍历。这样就能保证遍历处理的顺序和嵌套的顺序一致。

def flat_list_v_3(the_list):
    now = the_list[:]
    res = []
    while now:
        head = now.pop(0)
        if isinstance(head, list):
            now = head+now
        else:
            res.append(head)
    return res

运行:

# before
a = ['this', 'is', ['a', ['sample', 'of', ['nested', 'lists'], ','],
                    'enjoy', ['it', 'and'], 'have'], 'fun']
# after
a = ['this', 'is', 'a', 'sample', 'of', 'nested', 'lists', ',',
     'enjoy', 'it', 'and', 'have', 'fun']

参考