13

Доброго времени суток всем.

Есть список:

lst = [1, [2, 3], 4, [[6, 7]]]

Его нужно привести к такому виду:

lst = [1, 2, 3, 4, 6, 7]

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

Использую Python 3.5

2

6 ответов 6

13

Для начала, вот версия, которая использует ветвления и циклы, чтобы было ясно ожидаемое поведение:

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—если истинно.

0
11

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
  • 1
    Можно ast.literal_eval вместо eval здесь использовать.
    – jfs
    30 окт 2016 в 15:20
  • Стоит явно упомянуть, что даже по супер низким стандартам решений, которым нельзя использовать "ветвление и циклы", манипуляция кода как простой строки совмещённое с eval() является грязным грязным хаком (после использования частные места могут отвалится)—вы предупреждены.
    – jfs
    30 окт 2016 в 20:17
2
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 - лучшие (ИМХО).

4
  • Мой комментарий к другому ответу тут также применим. Если вы хотите со строками работать и вас интересуют только целые числа, то можно упростить решение: list(map(int, re.findall(r'\d+', str(lst))))
    – jfs
    30 окт 2016 в 20:48
  • Что-то сомнительный ответ. Тут же даже с числами, в которых больше одной цифры, работать не будет?
    – Qwertiy
    30 окт 2016 в 20:49
  • @Qwertiy верно, хотя g.split(), вместо g.replace(" ", '') легко снимет это ограничение. (Если оставить в стороне сам факт, разумности с кодом как с простой строкой без структуры работать).
    – jfs
    30 окт 2016 в 20:54
  • минусовать ответ не нужно—код работает для примера из вопроса.
    – jfs
    30 окт 2016 в 23:13
1

Вам необходим рекурсивный обход элементов списка. К примеру:

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))
2
  • Автор же написал, что ветвления нельзя использовать.
    – Xander
    30 окт 2016 в 13:18
  • if S == []: вот так лучше не делать, гораздо "питонячее" так: if not S 30 окт 2016 в 13:35
0
def normalize(item):
    return flatten(item) if isinstance(item, list) else [item]

def flatten(tree):
    return sum(map(normalize, tree), [])
1
0
# numpy - быстро и хорошо
# конкретно для данного случая не годится, ну или годится с изменениями
# длины членов массива должны совпадать, 
# а чаще всего так и бывает

import numpy as np
lst_np = np.array(lst)
lst_r = list(lst_np.ravel())
2

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.