Сгладить неправильный список списков

Я новичок в Python и пришел из прошлого. Это то, что я придумал (посмотрите названия вар для 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]

Кажется, работает. Тест:

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

возвращает:

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

L2 = [o for k in [[j] if not isinstance(j,list) else j for j in [k for i in [[m] if not 
isinstance(m,list) else m for m in L] for k in i]] for o in k]

Вот еще один подход 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) против 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

Это сгладит список или словарь (или список списков или словарей словарей и т. Д.). Предполагается, что значения являются строками, и создается строка, которая объединяет каждый элемент с аргументом-разделителем. Если вы хотите, вы можете использовать разделитель, чтобы потом разделить результат на объект списка. Он использует рекурсию, если следующим значением является список или строка. Используйте аргумент key, чтобы указать, хотите ли вы получить ключи или значения (установите для ключа значение false) из объекта словаря.

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=', ')

дает:

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

Мое решение:

import collections


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

немного более лаконично, но в значительной степени одинаково.

Если вам нравится рекурсия, это может быть решением для вас интереса:

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

Я фактически адаптировал это из некоторой практической схемы кода, который я написал некоторое время.

Наслаждайтесь!

Эта версия flatten позволяет избежать лимита рекурсии питона (и, таким образом, работает с произвольно глубокими, вложенными итерабелями). Это генератор, который может работать со строками и произвольными итерабелями (даже с бесконечными).

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

Генераторная версия не рекурсивного решения @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)

def nested_list(depth):
    l = [depth]
    for i in range(depth-1, 0, -1):
        l = [i, l]
    return l

nested_list(10)

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

def Flatten(ul):
    fl = []
    for i in ul:
        if type(i) is list:
            fl += Flatten(i)
        else:
            fl += [i]
    return fl

Flatten(nested_list(10))

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

Сравнительное тестирование

l = nested_list(100)

https://Вµs В± 14.3 Вµs stackoverflow.com/a/2158532

import collections

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

%%timeit -n 1000
list(flatten(l))

320 на цикл (означают В± станд. dev. 7 выполнений, 1 000 циклов каждый)

%%timeit -n 1000
Flatten(l)

60 Вµs В± 10.2 Вµs на цикл (означают В± станд. dev. 7 выполнений, 1 000 циклов каждый)

list(flatten(l)) == Flatten(l)

Верный

Думание, что следующее, вероятно, работало бы в python 3:

def get_flat_iter(xparent):
    try:
        r = xparent
        if hasattr(xx, '__iter__'):
            iparent = iter(xparent)
            if iparent != xparent:
                r = map(a, xparent)
    finally:
         pass
    return r

irregular_list = [1, [2, [3, 4]]]
flat_list = list(irregular_list)
print(flat_list) # [1, 2, 3, 4]