Flatten вложенного списка

Flatten вложенного списка

Проблема

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

1. Рекурсивное решение (самое простое)

def flatten_recursive(lst):
    """
    Рекурсивное решение для flatten.
    
    Временная сложность: O(N), где N — все элементы
    Пространственная: O(D), где D — максимальная глубина (call stack)
    """
    result = []
    
    for item in lst:
        if isinstance(item, list):
            # Рекурсивно flatten вложенный список
            result.extend(flatten_recursive(item))
        else:
            # Добавляем обычный элемент
            result.append(item)
    
    return result

# Примеры
print(flatten_recursive([1, [2, [3, 4], 5], 6]))
# [1, 2, 3, 4, 5, 6]

print(flatten_recursive([[1, 2], [3, [4, 5]]]))
# [1, 2, 3, 4, 5]

print(flatten_recursive([1, 2, 3]))
# [1, 2, 3]

print(flatten_recursive([[[[[1]]], 2]]))
# [1, 2]

Как работает:

1. Проходим по каждому элементу списка
2. Если элемент — список → рекурсивно вызываем flatten
3. Если обычный элемент → добавляем в результат
4. Возвращаем результат

2. List Comprehension (одна строка)

def flatten_list_comp(lst):
    """
    Решение с list comprehension (более Pythonic).
    """
    return [x for item in lst for x in (flatten_list_comp(item) if isinstance(item, list) else [item])]

# или более читаемо
def flatten_list_comp_readable(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend([x for sublist in flatten_list_comp_readable([item]) for x in sublist])
        else:
            result.append(item)
    return result

3. Генератор (экономия памяти)

def flatten_generator(lst):
    """
    Генератор для больших списков (экономит память).
    Возвращает элементы по одному вместо создания всего списка.
    """
    for item in lst:
        if isinstance(item, list):
            yield from flatten_generator(item)  # Рекурсивный yield
        else:
            yield item

# Использование
for element in flatten_generator([1, [2, [3, 4], 5], 6]):
    print(element)  # 1, 2, 3, 4, 5, 6

# Или как список
result = list(flatten_generator([1, [2, [3, 4], 5], 6]))
print(result)  # [1, 2, 3, 4, 5, 6]

Преимущества генератора:

• Не хранит весь результат в памяти
• Для больших списков (миллионы элементов) экономит RAM
• Ленивые вычисления (элементы генерируются по запросу)

4. Итеративное решение со стеком (для больших глубин)

def flatten_iterative(lst):
    """
    Итеративное решение с явным стеком (не рекурсия).
    Избегает stack overflow при очень большой глубине.
    """
    stack = [lst]  # Начинаем со списка
    result = []
    
    while stack:
        current = stack.pop()  # Берем последний элемент
        
        for item in reversed(current):  # Iterate in reverse (ВАЖНО!)
            if isinstance(item, list):
                stack.append(item)  # Добавляем подсписок в стек
            else:
                result.append(item)
    
    return result

# Примеры
print(flatten_iterative([1, [2, [3, 4], 5], 6]))
# [1, 2, 3, 4, 5, 6]

Почему reversed()? Потому что мы используем стек (LIFO), а нам нужен порядок слева направо.

5. Обработка разных типов коллекций

def flatten_general(lst, ignore_strings=True):
    """
    Более общее решение — обрабатывает tuple, set и другие коллекции.
    
    ignore_strings=True → не разворачиваем строки на символы
    """
    result = []
    
    for item in lst:
        # Проверяем, это итерируемый объект (но не строка)
        if isinstance(item, (list, tuple, set)):
            result.extend(flatten_general(item, ignore_strings))
        elif ignore_strings or not isinstance(item, str):
            result.append(item)
        else:
            result.append(item)
    
    return result

# Примеры
print(flatten_general([1, (2, [3, 4]), {5}]))
# [1, 2, 3, 4, 5]

print(flatten_general([1, "hello", [2, 3]]))
# [1, "hello", 2, 3]  (строка не разворачивается)

6. С использованием itertools

from itertools import chain

def flatten_itertools(lst):
    """
    Решение с itertools (более функциональный стиль).
    """
    for item in lst:
        if isinstance(item, list):
            yield from flatten_itertools(item)
        else:
            yield item

# Или с chain
def flatten_chain(lst):
    def _flatten(l):
        for item in l:
            if isinstance(item, list):
                yield from chain.from_iterable(map(_flatten, [item]))
            else:
                yield item
    return list(_flatten(lst))

7. NumPy (для числовых данных)

import numpy as np

def flatten_numpy(lst):
    """
    Для числовых списков — использовать NumPy (очень быстро).
    """
    arr = np.array(lst, dtype=object)  # dtype=object для смешанных типов
    return arr.flatten().tolist()

# Пример
print(flatten_numpy([1, [2, [3, 4]], 5]))
# [1, 2, 3, 4, 5]

Сравнение подходов

Граничные случаи

# Пустой список
flatten_recursive([])
# []

# Список без вложений
flatten_recursive([1, 2, 3])
# [1, 2, 3]

# Очень глубокая вложенность
flatten_recursive([[[[[[[1]]]]]]])
# [1]

# Пустые вложенные списки
flatten_recursive([1, [], [2, []], 3])
# [1, 2, 3]

# Смешанные типы
flatten_recursive([1, "hello", [2, [3.14, None]], True])
# [1, "hello", 2, 3.14, None, True]

Тестирование

import pytest

def test_flatten():
    assert flatten_recursive([1, [2, 3], 4]) == [1, 2, 3, 4]
    assert flatten_recursive([[1, 2], [3, 4]]) == [1, 2, 3, 4]
    assert flatten_recursive([1, [2, [3, 4]], 5]) == [1, 2, 3, 4, 5]
    assert flatten_recursive([]) == []
    assert flatten_recursive([1, 2, 3]) == [1, 2, 3]
    assert flatten_recursive([[[[[1]]]]]) == [1]
    assert flatten_recursive([1, [], [2, []], 3]) == [1, 2, 3]

def test_flatten_generator():
    assert list(flatten_generator([1, [2, 3], 4])) == [1, 2, 3, 4]
    assert list(flatten_generator([1, [2, [3, 4]], 5])) == [1, 2, 3, 4, 5]

На собеседовании

Что показать:

# Первый вариант — простой и правильный
def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

Если спросят оптимизацию:

1. "Для больших данных можно использовать генератор"
2. "Для очень глубоких списков — итеративный подход со стеком"
3. "Если это числовые данные — NumPy"

Если спросят про недостатки рекурсии:

• Stack overflow при глубине > 1000
• Решение: итеративный подход с явным стеком