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

Question

Да, я знаю, что этот предмет уже освещался ( здесь , здесь , здесь , здесь ), но насколько как я знаю, все решения, кроме одного, терпят неудачу в списке, подобном этому:

L = [[[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

flatten(L)

Это лучшая модель? Я что-то упустил? Есть проблемы?

Answer 1

Использование функций генератора может немного облегчить чтение вашего примера и, вероятно, повысить производительность.

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

Я использовал Iterable ABC , добавленный в 2.6.

Python 3

В Python 3 basestring больше не существует, но вы можете использовать кортеж str и bytes, чтобы получить тот же эффект.

Оператор yield from возвращает элемент из генератора по одному. Этот синтаксис для делегирования подгенерирующему был добавлен в 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

Answer 2

Мое решение:

import collections


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

Чуть более лаконично, но почти так же.

Answer 3

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

Answer 4

Генератор, использующий рекурсию и утку (обновлен для 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]

Answer 5

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

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

Answer 6

Вот моя функциональная версия рекурсивного сглаживания, которая обрабатывает как кортежи, так и списки, и позволяет добавлять любые сочетания позиционных аргументов. Возвращает генератор, который производит всю последовательность в порядке, arg by arg:

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

Использование:

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]

Answer 7

Вот еще один ответ, который еще более интересен ...

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)

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

Answer 8

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

Answer 9

Вы можете использовать deepflatten из пакета стороннего поставщика 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]

Это итератор, поэтому вам нужно повторить его (например, обернув его list или используя его в цикле). Внутренне он использует итеративный подход вместо рекурсивного подхода и записывается как расширение C, поэтому он может быть быстрее, чем подходы чистого Python:

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

---

Я являюсь автором библиотеки iteration_utilities.

Answer 10

Было забавно пытаться создать функцию, которая могла бы сгладить неправильный список в Python, но, конечно, это то, для чего предназначен Python (чтобы программирование было увлекательным). Следующий генератор работает довольно хорошо с некоторыми оговорками:

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

Это сгладит типы данных, которые вы можете оставить в покое (например, объекты bytearray, bytes и str). Кроме того, код опирается на тот факт, что запрос итератора из неповторяемого вызывает 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]
>>>

---

Изменить:

Я не согласен с предыдущей реализацией. Проблема в том, что вы не должны быть в состоянии сгладить то, что не повторяется. Это сбивает с толку и дает неправильное впечатление от аргумента.

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

Следующий генератор почти такой же, как первый, но у него нет проблемы с попыткой выравнивания не повторяемого объекта. Он терпит неудачу, как и следовало ожидать, когда ему дается неуместный аргумент.

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

Тестирование генератора работает нормально с предоставленным списком. Тем не менее, новый код вызовет TypeError, когда ему дается не повторяемый объект. Ниже показан пример нового поведения.

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