#python #алгоритм #python_3x #list
Доброго времени суток всем.
Есть список:
lst = [1, [2, 3], 4, [[6, 7]]]
Его нужно привести к такому виду:
lst = [1, 2, 3, 4, 6, 7]
При этом нельзя использовать ветвления и циклы, только стандартные методы. Задачка
простая, но взорвала мой мозг, может более опытные товарищи помогут?
Использую Python 3.5
Ответы
Ответ 1
just for fun =) flatten = lambda lst :eval('['+str(lst).replace('[','').replace(']','')+']') flat_list = flatten(lst) Но лучше не использовать eval() в вашем коде, подробнее здесь Ну или так (можно указать несколько типов): flatten = lambda lst: isinstance(lst, (int, str, float, bool)) and [lst] or sum(map(flatten, lst), []) lst = ["a", [2.3, True], 'abc', [[6, 7]]] flat_list = flatten(lst) print(flat_list) ['a', 2.3, True, 'abc', 6, 7]Ответ 2
Для начала, вот версия, которая использует ветвления и циклы, чтобы было ясно ожидаемое поведение: 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—если истинно.Ответ 3
Вам необходим рекурсивный обход элементов списка. К примеру: lst = [1, [2, 3], 4, [[6, 7]]] def lst_to_flat(S): if S == []: return S if isinstance(S[0], list): return lst_to_flat(S[0]) + lst_to_flat(S[1:]) return S[:1] + lst_to_flat(S[1:]) print(lst_to_flat(lst))Ответ 4
lst = [1, [2, 3], 4, [[6, 7]]] q = str(lst) a = q.replace("[",'') b = a.replace("]",'') g = b.replace(",",'') y = g.replace(" ",'') s = list(map(int, list( y ))) print (s) Посоветовал старший товарищ. Этот код не будет работать, если в изначальном массиве будут строки, числа и булевые значения, но для конкретного примера он сработает. Ответы senior-zero и jfs - лучшие (ИМХО).
Комментариев нет:
Отправить комментарий