Permutation

 Для пошаговой генерации перестановок в Python используется рекурсивная функция с ключевым словом yield, которая выдает новую комбинацию на каждом шаге, не сохраняя все варианты в памяти.

Код генератора перестановок

def permutations(data):
    # Базовый случай: если остался один элемент или пусто, возвращаем его
    if len(data) <= 1:
        yield data
    else:
        # Перебираем каждый элемент в качестве кандидата на первое место
        for i in range(len(data)):
            current = data[i]
            # Формируем хвост из всех остальных элементов
            remaining = data[:i] + data[i+1:]
            
            # Рекурсивно генерируем перестановки для хвоста
            for p in permutations(remaining):
                # Объединяем текущий элемент с перестановкой хвоста
                yield [current] + p

---

Пошаговый разбор работы (на примере [1, 2, 3])

Когда вы вызываете функцию и запрашиваете элементы через next(), выполнение происходит по следующему алгоритму:

1. Фиксация первого элемента (i = 0):
   • current становится 1.
   • remaining (остаток) равен [2, 3].
   • Функция рекурсивно уходит в permutations([2, 3]).
2. Шаг внутри рекурсии для [2, 3]:
   • Берется 2. Остаток [3]. Длина остатка равна 1 — срабатывает базовый случай (yield [3]).
   • К 2 прибавляется [3]. Получаем [2, 3].
   • Возвращаемся на верхний уровень, склеиваем с 1: yield [1, 2, 3] (Код засыпает).
3. Следующий шаг (next()):
   • Код просыпается внутри permutations([2, 3]). Цикл переходит к i = 1.
   • Берется 3. Остаток [2]. Базовый случай дает [2].
   • Склеиваем: 3 + [2] = [3, 2].
   • На верхнем уровне склеиваем с 1: yield [1, 3, 2] (Код засыпает).
4. Смена главного элемента (i = 1 на верхнем уровне):
   • Главный цикл функции permutations([1, 2, 3]) смещается. Теперь current равен 2.
   • remaining равен [1, 3]. Процесс повторяется, выдавая [2, 1, 3], а затем [2, 3, 1].
5. Последний элемент (i = 2 на верхнем уровне):
   • current равен 3, remaining равен [1, 2]. Генерируются варианты [3, 1, 2] и [3, 2, 1].

---

Как запустить генератор пошагово

Вы можете получать элементы вручную с помощью встроенной функции next(), что наглядно демонстрирует "замораживание" состояния:

# Инициализируем генератор
gen = permutations([1, 2, 3])

# Получаем элементы строго по одному вручную
print("Шаг 1:", next(gen))  # Выведет: [1, 2, 3]
print("Шаг 2:", next(gen))  # Выведет: [1, 3, 2]
print("Шаг 3:", next(gen))  # Выведет: [2, 1, 3]

# Можно перебрать оставшиеся через обычный цикл
print("--- Оставшиеся шаги в цикле ---")
for p in gen:
    print(p)

Альтернатива из стандартной библиотеки

Если вам нужен готовый инструмент для рабочих задач, используйте функцию permutations из встроенного модуля itertools — она также работает как эффективный пошаговый генератор:

from itertools import permutations

# itertools.permutations возвращает итератор (генератор)
for p in permutations([1, 2, 3]):
    print(list(p))

Если вам интересно, напишите: хотим ли мы добавить в этот код обработку дубликатов (например, для списка [1, 1, 2]) или вам нужно визуализировать дерево рекурсии для этого алгоритма?