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

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

Хотя был выбран элегантный и очень питонический ответ, я бы представил свое решение только для обзора:

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

Скажите, пожалуйста, насколько хорош или плох этот код?

Answer 2

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

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

Answer 3

Я предпочитаю простые ответы. Нет генераторов. Нет рекурсии или рекурсивных ограничений. Просто итерация:

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

Это работает с двумя списками: внутренний цикл for и внешний цикл while.

Внутренний цикл for просматривает список. Если он находит элемент списка, он (1) использует list.extend () для выравнивания этой части первого уровня вложенности и (2) переключает keepChecking в True. keepchecking используется для управления внешним циклом while. Если внешний цикл установлен в значение true, он запускает внутренний цикл для следующего прохода.

Эти проходы продолжаются до тех пор, пока не будут найдены вложенные списки. Когда, наконец, происходит проход, где ничего не найдено, keepChecking никогда не получает значение true, что означает, что listIsNested остается false, а внешний цикл while завершается.

Затем возвращается плоский список.

Тестовый прогон

flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

Answer 4

Вот реализация 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.

Answer 5

Я не просмотрел все уже имеющиеся ответы здесь, но вот один из предложенных мной вариантов, позаимствованный из способа обработки первого и остальных списков в 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]
>>> 

Answer 6

Я удивлен, что никто не подумал об этом. Чертова рекурсия Я не получаю рекурсивных ответов, которые сделали продвинутые люди здесь. в любом случае, вот моя попытка на это. Предостережение: оно очень специфично для варианта использования ОП

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]

Answer 7

Вот еще один подход 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) против 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

Answer 8

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

flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list)))

Answer 9

Я использовал рекурсив для решения вложенного списка с любой глубиной

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]

Answer 10

Просто используйте библиотеку funcy: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list