Напишите генератор, который развернет список любой вложенности в плоскую последовательность
Проверила команда Сопровод · Обновлено
Короткий ответ
Пройдите по элементам списка: если элемент сам список или кортеж, передайте его в тот же генератор через yield from, иначе отдайте элемент через yield. Пустые списки ничего не отдадут и пропадут сами. Строку не проверяйте вопросом «итерируема ли она»: она состоит из строк и уведет рекурсию в бесконечность. Память растет с глубиной вложенности, а не с длиной списка.
Почему этот вопрос задают
Задача проверяет сразу рекурсию, генераторы и внимание к типам. Дерево категорий, вложенные меню и JSON из внешних API приходят именно в таком виде, и разворачивать их приходится часто.
Условие задачи
Каталог строительного магазина хранит категории деревом: подкатегории лежат во вложенных списках, глубина не ограничена. Напишите генератор flatten(items), который отдает названия категорий по порядку в одну плоскую последовательность. Пустые подкатегории пропускайте, строки не разбивайте на буквы. Проверьте на каталоге ["Инструменты", ["Дрели", ["Перфораторы"]], [], "Краски"]: ожидается «Инструменты / Дрели / Перфораторы / Краски».
Как подойти к решению
- Пройдите по элементам списка циклом
forи проверьте тип каждого - Передайте вложенный список или кортеж в тот же генератор через
yield from - Отдайте через
yieldвсе остальное: строки, числа, объекты - Проверьте пустые списки и строки: обход не должен на них ломаться
- Покажите ленивость: возьмите два первых значения через
next
Решение
Каждое значение генератор отдает сразу, без промежуточных списков: два вызова next прошли только начало каталога. Пустые списки и кортежи дают пустой результат. Время O(n × d): значение поднимается через цепочку из d вложенных генераторов, и для каталога в 3–4 уровня это почти O(n). Память O(d) на эту цепочку.
def flatten(items):
for item in items:
if isinstance(item, (list, tuple)):
yield from flatten(item)
else:
yield item
catalog = ["Инструменты", ["Дрели", ["Перфораторы"]], [], "Краски"]
print(" / ".join(flatten(catalog)))
names = flatten(catalog)
print(next(names), next(names))
print(list(flatten([[], [[]], ()])))Инструменты / Дрели / Перфораторы / Краски Инструменты Дрели []
Что спросят следом
Что будет, если вложенность больше тысячи уровней?
Как разворачивать любые итерируемые объекты, а не только списки?
Чем
yield fromотличается от циклаfor x in flatten(item): yield x?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«Проверю, итерируемый ли элемент, через
iter(item)»Строка итерируема, ее символ тоже строка, и такой генератор уйдет в рекурсию до
RecursionError. Проверяйте конкретные типы или исключайтеstrиbytesявно«Склею все через
sum(catalog, [])»sumснимает только один уровень и падает сTypeError, если рядом со списками лежат строки. К тому же каждое сложение копирует список, и время растет квадратично«Проверю через
type(item) == list»Такая проверка пропустит подклассы списка и кортежи. Берите
isinstanceс кортежем типов:isinstance(item, (list, tuple))«Генератор и функция со списком — одно и то же, просто синтаксис другой»
Генератор отдает значения по одному и не держит весь результат в памяти. Его можно остановить после первых значений, и остальная часть дерева не будет пройдена
Сигналы для интервьюера
Сильный ответ
Сам называет ловушку со строками, проверяет пустые списки и предлагает обход без рекурсии для глубоких деревьев
Тревожный сигнал
Пишет верный генератор, но на вопрос, что делает yield from, отвечает только «так короче»
Красный флаг
Вынимает элементы из исходного каталога через pop во время обхода и портит данные вызывающего кода
Как еще могут спросить
- Как сделать плоский список из вложенного в Python?
- Напишите функцию
flattenдля списка произвольной вложенности - Как развернуть многоуровневый список с помощью
yield from? - Как превратить список списков любой глубины в одну последовательность?











