Achatar uma lista irregular de listas

Sim, eu sei que esse assunto já foi abordado antes ( aqui , aqui , aqui , aqui ), mas, tanto quanto eu sei, todas as soluções, exceto uma, falham em uma lista como esta:

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

Onde a saída desejada é

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

Ou talvez ainda melhor, um iterador. A única solução que vi que funciona para um aninhamento arbitrário é encontrada nesta pergunta :

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

flatten(L)

Este é o melhor modelo? Eu esqueci alguma coisa? Quaisquer problemas?

O uso das funções do gerador pode facilitar a leitura do seu exemplo e provavelmente aumentar o desempenho.

Python 2

def flatten(l):
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, basestring):
            for sub in flatten(el):
                yield sub
        else:
            yield el

Eu usei o ABC Iterável adicionado no 2.6.

Python 3

No Python 3, basestringnão existe mais, mas você pode usar uma tupla de stre bytesobter o mesmo efeito lá.

O yield fromoperador retorna um item de um gerador, um de cada vez. Esta sintaxe para delegar a um subgerador foi adicionada no 3.3

def flatten(l):
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el

Minha solução:

import collections


def flatten(x):
    if isinstance(x, collections.Iterable):
        return [a for i in x for a in flatten(i)]
    else:
        return [x]

Um pouco mais conciso, mas praticamente o mesmo.

Gerador usando recursão e digitação de patos (atualizado para Python 3):

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

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

Versão do gerador da solução não recursiva do @ unutbu, conforme solicitado por @Andrew em um comentário:

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

Versão ligeiramente simplificada deste gerador:

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)

Aqui está minha versão funcional do achatamento recursivo, que lida com tuplas e listas, e permite que você use qualquer combinação de argumentos posicionais. Retorna um gerador que produz toda a sequência em ordem, arg por arg:

flatten = lambda *n: (e for a in n
    for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,)))

Uso:

l1 = ['a', ['b', ('c', 'd')]]
l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)]
print list(flatten(l1, -2, -1, l2))
['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Esta versão flattenevita o limite de recursão do python (e, portanto, funciona com iteráveis ​​aninhados arbitrariamente profundos). É um gerador que pode lidar com strings e iterables arbitrários (mesmo os infinitos).

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

Aqui estão alguns exemplos que demonstram seu uso:

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]

Embora flattenpossa manipular geradores infinitos, ele não pode manipular aninhamentos infinitos:

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

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

Aqui está outra resposta que é ainda mais interessante ...

import re

def Flatten(TheList):
    a = str(TheList)
    b,crap = re.subn(r'[\[,\]]', ' ', a)
    c = b.split()
    d = [int(x) for x in c]

    return(d)

Basicamente, ele converte a lista aninhada em uma seqüência de caracteres, usa um regex para remover a sintaxe aninhada e depois converte o resultado novamente em uma lista (nivelada).

def flatten(xs):
    res = []
    def loop(ys):
        for i in ys:
            if isinstance(i, list):
                loop(i)
            else:
                res.append(i)
    loop(xs)
    return res

Você pode usar deepflattendo pacote de terceiros iteration_utilities:

>>> from iteration_utilities import deepflatten
>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(deepflatten(L))
[1, 2, 3, 4, 5, 6]

>>> list(deepflatten(L, types=list))  # only flatten "inner" lists
[1, 2, 3, 4, 5, 6]

É um iterador, portanto você precisa iterá-lo (por exemplo, envolvendo-o listou usando-o em um loop). Internamente, ele usa uma abordagem iterativa em vez de uma abordagem recursiva e é escrito como extensão C, para que seja mais rápido que as abordagens python puras:

>>> %timeit list(deepflatten(L))
12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit list(deepflatten(L, types=list))
8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit list(flatten(L))   # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381
86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit list(flatten(L))   # Josh Lee - https://stackoverflow.com/a/2158522/5393381
107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit list(genflat(L, list))  # Alex Martelli - https://stackoverflow.com/a/2159079/5393381
23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Eu sou o autor da iteration_utilitiesbiblioteca.

Foi divertido tentar criar uma função que pudesse achatar uma lista irregular no Python, mas é claro que é para isso que serve o Python (para tornar a programação divertida). O gerador a seguir funciona bastante bem com algumas ressalvas:

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

Ele vai achatar tipos de dados que você talvez queira ficar sozinho (como bytearray, bytese strobjetos). Além disso, o código se baseia no fato de que solicitar um iterador de um não-iterável gera a 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]
>>>

Editar:

Não concordo com a implementação anterior. O problema é que você não deve conseguir achatar algo que não é iterável. É confuso e dá a impressão errada do argumento.

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

O gerador a seguir é quase o mesmo que o primeiro, mas não tem o problema de tentar achatar um objeto não iterável. Ele falha como seria de esperar quando um argumento inapropriado é dado a ele.

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

Testar o gerador funciona bem com a lista fornecida. No entanto, o novo código gerará um TypeErrorquando um objeto não iterável é fornecido a ele. Exemplos são mostrados abaixo do novo comportamento.

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

Embora uma resposta elegante e muito pitônica tenha sido selecionada, eu apresentaria minha solução apenas para a revisão:

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

Por favor, diga o quão bom ou ruim é esse código?

Eu prefiro respostas simples. Sem geradores. Sem limites de recursão ou recursão. Apenas iteração:

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

Isso funciona com duas listas: um loop for interno e um loop while externo.

O loop for interno percorre a lista. Se ele encontrar um elemento de lista, (1) usa list.extend () para nivelar a parte um nível de aninhamento e (2) alterna keepChecking para True. keepchecking é usado para controlar o loop while externo. Se o loop externo for definido como true, ele acionará o loop interno para outra passagem.

Esses passes continuam acontecendo até que nenhuma lista aninhada seja encontrada. Quando uma passagem finalmente ocorre onde nenhuma é encontrada, keepChecking nunca é acionado como true, o que significa que listIsNested permanece falso e o loop while externo é encerrado.

A lista nivelada é então retornada.

Execução de teste

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

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

Aqui está uma função simples que nivela listas de profundidade arbitrária. Sem recursão, para evitar o estouro da pilha.

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

Estou surpreso que ninguém tenha pensado nisso. Maldita recursão, não recebo as respostas recursivas que as pessoas avançadas aqui fizeram. de qualquer maneira aqui está a minha tentativa sobre isso. ressalva é que é muito específico para o caso de uso do OP

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)

resultado:

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

Eu não passei por todas as respostas já disponíveis aqui, mas aqui está uma lista que eu inventei, tomando emprestado da maneira do lisp de processar o primeiro e o resto da lista

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

aqui está um caso simples e um não tão simples -

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

Ao tentar responder a essa pergunta, você realmente precisa fornecer as limitações do código que propõe como solução. Se fosse apenas sobre performances, eu não me importaria muito, mas a maioria dos códigos propostos como solução (incluindo a resposta aceita) falha ao achatar qualquer lista com profundidade maior que 1000.

Quando digo a maioria dos códigos quero dizer todos os códigos que usam qualquer forma de recursão (ou chamam uma função de biblioteca padrão que é recursiva). Todos esses códigos falham porque, para cada chamada recursiva feita, a pilha (chamada) cresce em uma unidade e a pilha de chamadas python (padrão) tem um tamanho de 1000.

Se você não estiver muito familiarizado com a pilha de chamadas, talvez o seguinte ajude (caso contrário, você pode simplesmente rolar para a Implementação ).

Tamanho da pilha de chamadas e programação recursiva (analogia do calabouço)

Encontrar o tesouro e sair

Imagine que você entra em uma enorme masmorra com salas numeradas , procurando um tesouro. Você não conhece o lugar, mas tem algumas indicações sobre como encontrar o tesouro. Cada indicação é um enigma (a dificuldade varia, mas você não pode prever o quão difícil será). Você decide pensar um pouco sobre uma estratégia para economizar tempo, faz duas observações:

1. É difícil (longo) encontrar o tesouro, pois você terá que resolver enigmas (potencialmente difíceis) para chegar lá.
2. Uma vez que o tesouro encontrado, retornar à entrada pode ser fácil, basta usar o mesmo caminho na outra direção (embora isso precise de um pouco de memória para recuperar o seu caminho).

Ao entrar na masmorra, você nota um pequeno caderno aqui. Você decide usá-lo para anotar todas as salas que sair depois de resolver um enigma (ao entrar em uma nova sala), dessa forma você poderá voltar para a entrada. Essa é uma ideia genial, você nem gasta um centavo implementando sua estratégia.

Você entra na masmorra, resolvendo com grande sucesso os primeiros 1001 enigmas, mas aí vem algo que você não havia planejado, não havia mais espaço no caderno emprestado. Você decide abandonar sua missão, pois prefere não ter o tesouro do que se perder para sempre dentro da masmorra (que parece realmente inteligente).

Executando um programa recursivo

Basicamente, é exatamente a mesma coisa que encontrar o tesouro. A masmorra é a memória do computador , seu objetivo agora não é encontrar um tesouro, mas calcular algumas funções (encontre f (x) para um dado x ). As indicações são simplesmente sub-rotinas que o ajudarão a resolver f (x) . Sua estratégia é a mesma da pilha de chamadas , o notebook é a pilha, as salas são os endereços de retorno das funções:

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

O problema que você encontrou no calabouço será o mesmo aqui, a pilha de chamadas tem um tamanho finito (aqui 1000) e, portanto, se você digitar muitas funções sem retornar, preencherá a pilha de chamadas e ocorrerá um erro que parecerá como "Caro aventureiro, sinto muito, mas seu notebook está cheio" :RecursionError: maximum recursion depth exceeded . Observe que você não precisa de recursão para preencher a pilha de chamadas, mas é muito improvável que um programa não recursivo chame 1000 funções sem nunca retornar. É importante entender também que, quando você retorna de uma função, a pilha de chamadas é liberada do endereço usado (daí o nome "pilha", o endereço de retorno é inserido antes de inserir uma função e retirado ao retornar). No caso especial de uma recursão simples (uma funçãofque se autodenomina repetidamente - você entrará frepetidamente até que o cálculo esteja concluído (até que o tesouro seja encontrado) e retornará de faté voltar ao local para o qual você ligou f. A pilha de chamadas nunca será liberada de nada até o final, onde será liberada de todos os endereços de retorno, um após o outro.

Como evitar esse problema?

Na verdade, isso é bem simples: "não use recursão se você não souber o quão profundo ela pode ser". Isso nem sempre é verdade, pois em alguns casos, a recursão da chamada de cauda pode ser otimizada (TCO) . Mas em python, esse não é o caso, e mesmo a função recursiva "bem escrita" não otimiza o uso da pilha. Há um post interessante de Guido sobre esta questão: Eliminação da recursão da cauda .

Existe uma técnica que você pode usar para tornar iterativa qualquer função recursiva, essa técnica que poderíamos chamar de trazer seu próprio notebook . Por exemplo, em nosso caso específico, simplesmente estamos explorando uma lista, entrar em uma sala é equivalente a entrar em uma sub-lista; a pergunta que você deve fazer é: como posso voltar de uma lista para sua lista de pais? A resposta não é tão complexa, repita o seguinte até que stackesteja vazio:

1. empurre a lista atual addresse indexem um stackao entrar em uma nova sub-lista (note que um endereço de lista + índice é também um endereço, portanto, apenas usar exatamente a mesma técnica usada pela pilha de chamadas);
2. toda vez que um item é encontrado, yieldele (ou adiciona-o a uma lista);
3. quando uma lista for totalmente explorada, volte à lista de pais usando o stack retorno address(e index) .

Observe também que isso é equivalente a um DFS em uma árvore em que alguns nós são sublistas A = [1, 2]e outros são itens simples: 0, 1, 2, 3, 4(para L = [0, [1,2], 3, 4]). A árvore fica assim:

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

A pré-ordem de travessia do DFS é: L, 0, A, 1, 2, 3, 4. Lembre-se de que, para implementar um DFS iterativo, você também "precisa" de uma pilha. A implementação que propus antes resulta em ter os seguintes estados (para stacke 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]

Neste exemplo, o tamanho máximo da pilha é 2, porque a lista de entrada (e, portanto, a árvore) possui profundidade 2.

Implementação

Para a implementação, em python, você pode simplificar um pouco usando iteradores em vez de listas simples. As referências aos (sub) iteradores serão usadas para armazenar os endereços de retorno das sublistas (em vez de ter o endereço da lista e o índice). Essa não é uma grande diferença, mas acho que é mais legível (e também um pouco mais rápida):

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)

Além disso, observe que em is_list_likeI have isinstance(item, list), que poderia ser alterado para lidar com mais tipos de entrada, aqui eu só queria ter a versão mais simples em que (iterável) seja apenas uma lista. Mas você também pode fazer isso:

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

Isso considera as strings como "itens simples" e, portanto flatten_iter([["test", "a"], "b]), retornará ["test", "a", "b"]e não ["t", "e", "s", "t", "a", "b"]. Observe que, nesse caso, iter(item)é chamado duas vezes em cada item, vamos fingir que é um exercício para o leitor tornar esse limpador mais limpo.

Testes e observações sobre outras implementações

No final, lembre-se de que você não pode imprimir uma lista infinitamente aninhada Lusando, print(L)porque internamente ela usará chamadas recursivas para __repr__( RecursionError: maximum recursion depth exceeded while getting the repr of an object). Pelo mesmo motivo, as soluções de flattenenvolvimento strfalharão com a mesma mensagem de erro.

Se você precisar testar sua solução, poderá usar esta função para gerar uma lista aninhada simples:

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

O que fornece: build_deep_list(5)>>> [4, [3, [2, [1, [0]]]]].

Aqui está a compiler.ast.flattenimplementação na 2.7.5:

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

Existem métodos melhores e mais rápidos (se você chegou aqui, já os viu)

Observe também:

Preterido desde a versão 2.6: O pacote do compilador foi removido no Python 3.

totalmente hacky, mas acho que funcionaria (dependendo do seu data_type)

flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list)))

Basta usar uma funcybiblioteca: pip install funcy

import funcy


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

Aqui está outra abordagem py2, não tenho certeza se é a mais rápida, a mais elegante nem a mais segura ...

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

Ele pode ignorar qualquer tipo específico (ou derivado) desejado, retorna um iterador, para que você possa convertê-lo em qualquer contêiner específico, como lista, tupla, ditado ou simplesmente consumi-lo para reduzir o consumo de memória, para melhor ou pior ele pode manipular objetos não-iteráveis ​​iniciais, como int ...

Observe que a maior parte do trabalho pesado é feita em C, já que, até onde eu sei, é implementado o itertec, por isso, embora seja recursivo, o AFAIK não é limitado pela profundidade da recursão do python, pois as chamadas de função estão acontecendo em C, embora isso não significa que você esteja limitado pela memória, especialmente no OS X, onde o tamanho da pilha tem um limite rígido a partir de hoje (OS X Mavericks) ...

existe uma abordagem um pouco mais rápida, mas um método menos portátil, use-o somente se você puder assumir que os elementos base da entrada podem ser explicitamente determinados, caso contrário, você obterá uma recursão infinita e o OS X com seu tamanho limitado de pilha será lançar uma falha de segmentação rapidamente ...

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

aqui estamos usando conjuntos para verificar o tipo, para que O (1) vs O (número de tipos) verifique se um elemento deve ou não ser ignorado, embora, é claro, qualquer valor com o tipo derivado dos tipos ignorados declarados falhe , é por isso que está usando str, unicodeentão use-o com cuidado ...

testes:

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

Sem usar nenhuma biblioteca:

def flat(l):
    def _flat(l, r):    
        if type(l) is not list:
            r.append(l)
        else:
            for i in l:
                r = r + flat(i)
        return r
    return _flat(l, [])



# example
test = [[1], [[2]], [3], [['a','b','c'] , [['z','x','y']], ['d','f','g']], 4]    
print flat(test) # prints [1, 2, 3, 'a', 'b', 'c', 'z', 'x', 'y', 'd', 'f', 'g', 4]

Usando itertools.chain:

import itertools
from collections import Iterable

def list_flatten(lst):
    flat_lst = []
    for item in itertools.chain(lst):
        if isinstance(item, Iterable):
            item = list_flatten(item)
            flat_lst.extend(item)
        else:
            flat_lst.append(item)
    return flat_lst

Ou sem encadeamento:

def flatten(q, final):
    if not q:
        return
    if isinstance(q, list):
        if not isinstance(q[0], list):
            final.append(q[0])
        else:
            flatten(q[0], final)
        flatten(q[1:], final)
    else:
        final.append(q)

Eu usei recursivo para resolver lista aninhada com qualquer profundidade

def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y):
    '''
    apply function: combiner to a nested list element by element(treated as flatten list)
    '''
    current_value=init
    for each_item in nlist:
        if isinstance(each_item,list):
            current_value =combine_nlist(each_item,current_value,combiner)
        else:
            current_value = combiner(current_value,each_item)
    return current_value

Então, depois de definir a função combine_nlist, é fácil usar esta função do flatting. Ou você pode combiná-lo em uma função. Eu gosto da minha solução porque ela pode ser aplicada a qualquer lista aninhada.

def flatten_nlist(nlist):
    return combine_nlist(nlist,[],lambda x,y:x+[y])

resultado

In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10])
Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

A maneira mais fácil é usar a biblioteca de metamorfose usando pip install morph.

O código é:

import morph

list = [[[1, 2, 3], [4, 5]], 6]
flattened_list = morph.flatten(list)  # returns [1, 2, 3, 4, 5, 6]

Estou ciente de que já existem muitas respostas impressionantes, mas eu gostaria de adicionar uma resposta que use o método de programação funcional para resolver a questão. Nesta resposta, uso dupla recursão:

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

resultado:

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

Não tenho certeza se isso é necessariamente mais rápido ou mais eficaz, mas é isso que eu faço:

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

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

A flattenfunção aqui transforma a lista em uma cadeia de caracteres, retira todos os colchetes, anexa colchetes de volta às extremidades e a transforma novamente em uma lista.

Embora, se você soubesse que teria colchetes na sua lista em cadeias de caracteres, [[1, 2], "[3, 4] and [5]"]teria que fazer outra coisa.

Este é um implemento simples de achatar em python2

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]

Isso achatará uma lista ou dicionário (ou lista de listas ou dicionários de dicionários etc.). Ele assume que os valores são cadeias e cria uma cadeia que concatena cada item com um argumento separador. Se você quiser, poderá usar o separador para dividir o resultado em um objeto de lista posteriormente. Ele usa recursão se o próximo valor for uma lista ou uma sequência. Use o argumento key para saber se você deseja as chaves ou os valores (defina key como false) do objeto de dicionário.

def flatten_obj(n_obj, key=True, my_sep=''):
    my_string = ''
    if type(n_obj) == list:
        for val in n_obj:
            my_sep_setter = my_sep if my_string != '' else ''
            if type(val) == list or type(val) == dict:
                my_string += my_sep_setter + flatten_obj(val, key, my_sep)
            else:
                my_string += my_sep_setter + val
    elif type(n_obj) == dict:
        for k, v in n_obj.items():
            my_sep_setter = my_sep if my_string != '' else ''
            d_val = k if key else v
            if type(v) == list or type(v) == dict:
                my_string += my_sep_setter + flatten_obj(v, key, my_sep)
            else:
                my_string += my_sep_setter + d_val
    elif type(n_obj) == str:
        my_sep_setter = my_sep if my_string != '' else ''
        my_string += my_sep_setter + n_obj
        return my_string
    return my_string

print(flatten_obj(['just', 'a', ['test', 'to', 'try'], 'right', 'now', ['or', 'later', 'today'],
                [{'dictionary_test': 'test'}, {'dictionary_test_two': 'later_today'}, 'my power is 9000']], my_sep=', ')

rendimentos:

just, a, test, to, try, right, now, or, later, today, dictionary_test, dictionary_test_two, my power is 9000

Se você gosta de recursão, isso pode ser uma solução interessante para você:

def f(E):
    if E==[]: 
        return []
    elif type(E) != list: 
        return [E]
    else:
        a = f(E[0])
        b = f(E[1:])
        a.extend(b)
        return a

Na verdade, adaptei isso a partir de algum código prático do esquema que havia escrito há algum tempo.

Aproveitar!

Eu sou novo em python e venho de um fundo lisp. Isto é o que eu vim com (confira os nomes de var para lulz):

def flatten(lst):
    if lst:
        car,*cdr=lst
        if isinstance(car,(list,tuple)):
            if cdr: return flatten(car) + flatten(cdr)
            return flatten(car)
        if cdr: return [car] + flatten(cdr)
        return [car]

Parece funcionar. Teste:

flatten((1,2,3,(4,5,6,(7,8,(((1,2)))))))

retorna:

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