Для начала, вот версия, которая использует ветвления и циклы, чтобы было ясно ожидаемое поведение:
from collections import Iterable
def flatten_gen(nested, isatom=lambda x: not isinstance(x, Iterable)):
for item in nested:
if isatom(item):
yield item
else:
yield from flatten_gen(item)
Пример:
lst = [1, [2, 3], 4, [[6, 7]]]
print(list(flatten_gen(lst)))
# -> [1, 2, 3, 4, 6, 7]
где isatom()
предикат определяет что является атомом (неразрывным объектом) с точки зрения этого метода. Подразумевается, что "не атомы" можно в цикл передать, чтобы получить объекты, из которых они состоят.
Алгоритм прямолинейный: перебирая элементы переданного списка, отдаём атомы как есть, а для составных объектов, вызываем генератор рекурсивно.
Так как строки по умолчанию работают с циклами, то если вы хотите их рассматривать как атомы в вашем случае, то передайте isatom
явно:
isatom = lambda x: isinstance(x, str) or not instance(x, Iterable)
Если только целые числа считаются атомами, то isatom = lambda x: isinstance(x, int)
.
Рекурсивная версия без явного ветвления, циклов, используя iterable unpacking синтакс:
def flatten(nested):
try:
first, *rest = nested
except TypeError: # not an iterable
return [nested]
except ValueError: # empty
return []
return flatten(first) + flatten(rest)
Код отпиливает первый элемент от заданного вложенного списка и соединяет плоский список, полученный из него с помощью рекурсивного вызова flatten(first)
, с плоским списком, полученным вызовом с остатком входного списка flatten(rest)
.
Если не получается отпилить первый элемент из-за того, что ввод пустой или скаляр дан (не перечислимое значение—число к примеру), то возвращается пустой список или этот скаляр внутри списка соответственно.
Если на входе вложенный список с числами, то на каждом уровне задача уменьшается до тех пор пока функция не будет вызвана с простейшими параметрами: число или пустой список, что приводит к возвращению конкретных значений и собиранию конечного результата при подъёме по стеку вызовов.
Данная реализация не работает со строками без адаптации, так как 'a' == 'a'[0]
(строка из одного символа равна своему первому символу)—это приводит к бесконечной рекурсии в данном случае.
Код не оптимален по производительности (для простоты), но нет if/else ветвлений и циклов.
Вот похожая, но более эффективная версия, которая использует генератор:
def flatten_gen(nested):
try:
it = iter(nested)
except TypeError: # not an iterable
yield nested
return
try:
first = next(it)
except StopIteration: # empty
return
yield from flatten_gen(first)
yield from flatten_gen(it)
Генератор пытается получить итератор it
с помощью iter(nested)
и если на входе скаляр (например, целое число), то выбрасывается TypeError
и генератор возвращает этот скаляр (yield
). next(it)
возвращает первый элемент из итератора, если он не пустой. Затем рекурсивно генерируются скаляры для первого элемента и оставшихся элементов в it
итераторе.
Если можно использовать циклы из библиотечного кода, наподобие sum(map(flatten, lst, []))
решения из @borisrozumnuk ответа, то можно улучшить flatten_gen()
генератор, используя itertools.chain()
:
from itertools import chain
def flatten_gen(nested):
try:
it = iter(nested)
except TypeError: # not an iterable
yield nested
else:
yield from chain.from_iterable(map(flatten_gen, it))
Так как рекурсия не используется в этом случае, чтобы цикл реализовать, то количество вызовов вдвое меньше.
Если хочется, можно в виде одного выражения записать:
def flatten(nested):
return (isinstance(nested, int) and [nested] # an int
or nested # empty
and flatten(nested[0]) + flatten(nested[1:])) # non-empty list
Что работает, благодаря short-circuit поведению and/or логических операторов. Не ясно рассматривать ли это как использование ветвления.
Если nested
это целое, то код возвращает это число, обёрнутое в список ([nested]
). Если nested
не целое число (а список), то он сразу возвращается, если он пустой (len(nested) == 0
означает, что bool(nested) is False
). Если nested
не пустой список, то возвращается объединение плоских списков, возвращаемое рекурсивными вызовами для первого элемента и остатка от списка—также как и в решениях выше в этом ответе.
Если двигаться дальше в сторону нечитаемости кода, то ветвление можно заменить с помощью индексирования списков и lambda
, чтобы задержать выполнение:
def flatten(nested):
return [
lambda: [ # list (not an int)
lambda: flatten(nested[0]) + flatten(nested[1:]), # non-empty list
lambda: [] # empty
][not nested](),
lambda: [nested] # an int
][isinstance(nested, int)]()
Общая идея: True == 1 and False == 0
в Питоне, поэтому выражение [on_false, on_true][condition]()
вызывает on_false
функцию, если condition
ложно и on_true
—если истинно.