Сгладить нерегулярный список списков
Да, я знаю, что этот вопрос был рассмотрен ранее (здесь, здесь, здесь, здесь), но, насколько я знаю, все решения, за исключением одного, выходят из списка следующим образом:
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)
Является ли это лучшей моделью? Я что-то пропустил? Любые проблемы?
Ответы
Ответ 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
Ответ 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]
Чуть более лаконично, но примерно так же.
Ответ 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)
Ответ 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]
Ответ 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
Ответ 6
Вот моя функциональная версия рекурсивной сглаживания, которая обрабатывает как кортежи, так и списки, и позволяет вам использовать любое сочетание позиционных аргументов. Возвращает генератор, который производит всю последовательность в порядке, arg 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]
Ответ 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)
В основном, он преобразует вложенный список в строку, использует регулярное выражение для выделения вложенного синтаксиса, а затем преобразует результат обратно в (сплющенный) список.
Ответ 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
Ответ 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.
Ответ 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]
>>>
Edit:
Я не согласен с предыдущей реализацией. Проблема в том, что вы не должны сглаживать то, что не является итерируемым. Это сбивает с толку и дает неправильное представление об этом аргументе.
>>> 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
>>>
Ответ 11
Хотя был выбран элегантный и очень пифонический ответ, я бы представил свое решение только для обзора:
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
Расскажите, насколько хорош или плох этот код?
Ответ 12
Я предпочитаю простые ответы. Нет генераторов. Ограничений рекурсии или рекурсии. Просто итерация:
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
Это работает с двумя списками: внутренним циклом и внешним циклом while.
Внутренний цикл цикла повторяется через список. Если он находит элемент списка, он (1) использует list.extend(), чтобы сгладить тот уровень, на котором один уровень вложенности, и (2) переключает keepChecking на True. keepchecking используется для управления внешним циклом while. Если внешний цикл получает значение true, он запускает внутренний цикл для другого прохода.
Эти проходы продолжаются до тех пор, пока не будут найдены больше вложенных списков. Когда пропуск, наконец, происходит там, где ни один не найден, keepChecking никогда не сработает до истины, что означает, что listIsNested остается ложным, а внешний while цикл выходит.
Затем возвращается сплющенный список.
Тестирование
flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
Ответ 13
Здесь простая функция, которая выравнивает списки произвольной глубины. Нет рекурсии, чтобы избежать.
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
Ответ 14
Здесь реализация compiler.ast.flatten в 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
Есть лучшие, более быстрые методы (если вы уже здесь, вы уже видели их)
Также обратите внимание:
Устаревший с версии 2.6: пакет компилятора был удален в Python 3.
Ответ 15
полностью взломан, но я думаю, что он будет работать (в зависимости от вашего data_type)
flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list)))
Ответ 16
Я удивлен, что никто не подумал об этом. Проклятая рекурсия. Я не получаю рекурсивных ответов, которые предлагали здесь продвинутые люди. В любом случае, вот моя попытка. оговорка это очень специфична для случая использования 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)
выход:
[1, 2, 3, 4, 5, 6]
Ответ 17
Я не рассмотрел все уже имеющиеся ответы здесь, но вот один лайнер, который я придумал, заимствуя из lisp способ первой и обработки списка отдыха
def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l]
вот один простой и один не очень простой случай -
>>> 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]
>>>
Ответ 18
При попытке ответить на такой вопрос вам действительно нужно указать ограничения кода, который вы предлагаете в качестве решения. Если бы речь шла только о выступлениях, я бы не прочь слишком много, но большинство кодов, предложенных как решение (включая принятый ответ), не сглаживают список, который имеет глубину более 1000.
Когда я говорю большинство кодов, я имею в виду все коды, которые используют любую форму рекурсии (или называют стандартную библиотечную функцию, которая является рекурсивной). Все эти коды терпят неудачу, потому что для каждого рекурсивного вызова стек (вызова) растет на единицу, а стек вызовов по умолчанию (по умолчанию) python имеет размер 1000.
Если вы не слишком хорошо знакомы с стеком вызовов, возможно, следующее поможет (иначе вы можете просто перейти к Реализации).
Размер стека вызовов и рекурсивное программирование (аналогия подземелий)
Поиск сокровищ и выход
Представьте, что вы входите в огромную подземелье с пронумерованными комнатами, ища сокровище. Вы не знаете места, но у вас есть некоторые указания о том, как найти сокровище. Каждое указание - загадка (трудности различаются, но вы не можете предсказать, насколько они будут тяжелыми). Вы решили немного подумать о стратегии экономии времени, вы делаете два наблюдения:
- Это трудно (долго) найти сокровище, как вам придется решать (потенциально трудно) загадки, чтобы добраться туда.
- Как только найденное сокровище, возвращение к входу может быть легким, вам просто нужно использовать тот же путь в другом направлении (хотя для этого требуется немного памяти, чтобы вспомнить ваш путь).
Когда вы входите в подземелье, вы замечаете здесь маленький ноутбук. Вы решили использовать его для записи каждой комнаты, которую вы выходите, после решения загадки (при входе в новую комнату), таким образом вы сможете вернуться обратно к входу. Это гениальная идея, вы даже не потратите цент, реализуя свою стратегию.
Вы попадаете в темницу, с большим успехом решаете первые 1001 загадки, но здесь приходит то, что вы не планировали, у вас нет места в записной книжке, которую вы заимствовали. Вы решаете отказаться от своего квеста, так как вы предпочитаете не иметь сокровища, чем быть потерянным навсегда внутри подземелья (это выглядит действительно умным).
Выполнение рекурсивной программы
В принципе, это то же самое, что найти сокровище. Подземелье - это компьютерная память, теперь ваша цель - не найти сокровище, а вычислить некоторую функцию (найти f (x) для данного x). Показания просто являются подпрограммами, которые помогут вам решить f (x). Ваша стратегия такая же, как стратегия стека вызовов, ноутбук - это стек, номера - это обратные адреса функций:
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 see what you've collected
print(' '.join(y))
Проблема, с которой вы столкнулись в подземелье, будет здесь же, стек вызовов имеет конечный размер (здесь 1000), и поэтому, если вы вводите слишком много функций, не возвращаясь обратно, вы заполняете стек вызовов и получаете ошибку, которая выглядит "Дорогой искатель приключений, мне очень жаль, но ваш ноутбук полон": RecursionError: maximum recursion depth exceeded. Обратите внимание, что вам не нужна рекурсия для заполнения стека вызовов, но очень маловероятно, что нерекурсивная программа вызовет 1000 функций, не возвращаясь. Важно также понимать, что после того, как вы вернулись из функции, стек вызовов освобождается от используемого адреса (отсюда имя "стек", адрес возврата вставляются перед входом в функцию и вытаскиваются при возврате). В частном случае простой рекурсии (функция f которая вызывает себя один раз - снова и снова) вы будете вводить f снова и снова, пока вычисление не закончится (пока сокровище не будет найдено) и не вернется с f до тех пор, пока вы не пойдете назад к месту, где вы назвали f в первую очередь. Стек вызовов никогда не будет освобожден от чего-либо до конца, где он будет освобожден от всех обратных адресов один за другим.
Как избежать этой проблемы?
Это на самом деле довольно просто: "не используйте рекурсию, если вы не знаете, как глубоко она может идти". Это не всегда так, как в некоторых случаях, рекурсия хвостового звонка может быть оптимизирована (TCO). Но в python это не так, и даже "хорошо написанная" рекурсивная функция не будет оптимизировать использование стека. Есть интересный пост от Гвидо об этом вопросе: " Устранение хвостовой рекурсии".
Существует методика, позволяющая сделать любую рекурсивную функцию итеративной, эта техника, которую мы могли бы назвать, приносит ваш собственный ноутбук. Например, в нашем конкретном случае мы просто изучаем список, входя в комнату, эквивалентно вводу подсписок, вопрос, который вы должны задать себе, - как я могу вернуться из списка в его родительский список? Ответ не такой сложный, повторите следующее, пока stack будет пустым:
- нажимайте текущий
address и index в stack при вводе нового подсписок (обратите внимание, что адрес + индекс также является адресом, поэтому мы используем только тот же метод, который используется стеком вызовов); - каждый раз, когда элемент найден,
yield его (или добавьте в список); - как только список будет полностью изучен, вернитесь к родительскому списку, используя
address возврата stack (и index).
Также обратите внимание, что это эквивалентно DFS в дереве, где некоторые узлы являются подсписками A = [1, 2] а некоторые являются простыми элементами: 0, 1, 2, 3, 4 (для L = [0, [1,2], 3, 4]). Дерево выглядит так:
L
|
-------------------
| | | |
0 --A-- 3 4
| |
1 2
Предварительный порядок обхода DFS: L, 0, A, 1, 2, 3, 4. Помните, что для реализации итеративной DFS вам также понадобится стек. Реализация, которую я предложил, flat_list к flat_list, что следующие состояния (для stack и 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]
В этом примере максимальный размер стека равен 2, так как список ввода (и, следовательно, дерево) имеет глубину 2.
Реализация
Для реализации в python вы можете немного упростить использование итераторов вместо простых списков. Ссылки на (югу) итераторы будут использоваться для хранения адресов подписок для возврата (вместо того, чтобы иметь как адрес списка, так и индекс). Это не большая разница, но я считаю, что это более читаемо (а также немного быстрее):
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)
Также обратите внимание, что в is_list_like меня есть isinstance(item, list), который можно изменить для обработки большего количества типов ввода, здесь я просто хотел иметь простейшую версию, где (iterable) является просто списком. Но вы также можете это сделать:
def is_list_like(item):
try:
iter(item)
return not isinstance(item, str) # strings are not lists (hmm...)
except TypeError:
return False
Это рассматривает строки как "простые элементы", и поэтому flatten_iter([["test", "a"], "b]) вернет ["test", "a", "b"] а не ["t", "e", "s", "t", "a", "b"]. Обратите внимание, что в этом случае iter(item) вызывается дважды на каждом элементе, пусть делает вид, что это упражнение для читателя, чтобы сделать это чище.
Тестирование и замечания по другим реализациям
Помните, что вы не можете напечатать бесконечно вложенный список L используя print(L) потому что внутри он будет использовать рекурсивные вызовы __repr__ (RecursionError: maximum recursion depth exceeded while getting the repr of an object). По той же причине решения flatten связанные с str выйдут с одинаковым сообщением об ошибке.
Если вам нужно протестировать свое решение, вы можете использовать эту функцию для создания простого вложенного списка:
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
Что дает: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]].
Ответ 19
Просто используйте библиотеку funcy: pip install funcy
import funcy
funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list
Ответ 20
Вот еще один подход 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) vs 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
Ответ 21
Я использовал рекурсивный для решения вложенный список с любой глубиной
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
Итак, после того, как я определяю функцию comb_nlist, легко использовать эту функцию для выравнивания. Или вы можете объединить его в одну функцию. Мне нравится мое решение, потому что оно может быть применено к любому вложенному списку.
def flatten_nlist(nlist):
return combine_nlist(nlist,[],lambda x,y:x+[y])
результат
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]
Ответ 22
Использование 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
Или без привязки:
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)
Ответ 23
Самый простой способ - использовать библиотеку morph, используя pip install morph.
Код:
import morph
list = [[[1, 2, 3], [4, 5]], 6]
flattened_list = morph.flatten(list) # returns [1, 2, 3, 4, 5, 6]
Ответ 24
Я знаю, что уже есть много замечательных ответов, но я хотел добавить ответ, который использует метод функционального программирования для решения вопроса. В этом ответе я использую двойную рекурсию:
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]]))
выход:
[1, 2, 3, 4, 5, 6, 7]
Ответ 25
Это сгладит список или словарь (или список списков или словарей словарей и т.д.). Предполагается, что значения являются строками, и создается строка, которая объединяет каждый элемент с аргументом-разделителем. Если вы хотите, вы можете использовать разделитель, чтобы потом разделить результат на объект списка. Он использует рекурсию, если следующим значением является список или строка. Используйте аргумент 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
Ответ 26
Я не уверен, что это обязательно быстрее или эффективнее, но это то, что я делаю:
def flatten(lst):
return eval('[' + str(lst).replace('[', '').replace(']', '') + ']')
L = [[[1, 2, 3], [4, 5]], 6]
print(flatten(L))
Функция flatten превращает список в строку, вытаскивает квадратные скобки all, привязывает квадратные скобки к концам и возвращает их обратно в список.
Хотя, если бы вы знали, что у вас будут квадратные скобки в вашем списке в строках, например [[1, 2], "[3, 4] and [5]"], вам нужно будет сделать что-то еще.
Ответ 27
Это простая реализация flatten на 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]
Ответ 28
Если вам нравится рекурсия, это может быть интересным для вас решением:
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
Я действительно адаптировал это из некоторого кода схемы практики, который я написал некоторое время назад.
Наслаждайтесь!
Ответ 29
Я новичок в python и исхожу из фона lisp. Это то, что я придумал (проверьте имена var для 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]
Ответ 30
Я не вижу ничего подобного в этом месте и только что получил здесь закрытый вопрос по тому же вопросу, но почему бы просто не сделать что-то подобное (если вы знаете тип списка, который хотите разбить):
>>> a = [1, 2, 3, 5, 10, [1, 25, 11, [1, 0]]]
>>> g = str(a).replace('[', '').replace(']', '')
>>> b = [int(x) for x in g.split(',') if x.strip()]
Вам нужно будет знать тип элементов, но я думаю, что это может быть обобщено, и с точки зрения скорости я думаю, что это будет быстрее.
