Построение перестановок

Перестановка — это расположение всех данных элементов в некотором порядке. На этой странице разберём, как с помощью рекурсии и возврата получить каждую перестановку ровно один раз и применить такой перебор к задачам ЕГЭ-24 и ЕГЭ-27.

Идея построения перестановки

Пусть дан набор различных элементов \(a_1, a_2, \ldots, a_n\). Перестановку удобно строить слева направо. На первой позиции можно выбрать любой элемент, на второй — любой ещё не использованный, затем на третьей — любой из оставшихся. Когда все позиции заполнены, получен один готовый вариант.

Здесь \(P_n\) — число всех перестановок. Например, для трёх букв существует \(3!=6\) нұсқа: ABC, ACB, BAC, BCA, CAB, CBA. Рекурсивная программа должна перебрать именно эти \(6\) листьев дерева нұсқа, не повторяя их.

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

Состояние и возврат

Для перебора достаточно хранить два объекта: текущую последовательность и множество использованных элементов. Это состояние перебора: состояние перебора описывает, где находится алгоритм и какие шешімдер уже приняты.

1. Выбрать элемент, который ещё не использован.
2. Добавить его в текущую последовательность и отметить использованным.
3. Рекурсивно заполнить следующую позицию.
4. Удалить элемент из последовательности и снять отметку использования.

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

1def generate(current, used):
2    if len(current) == n:
3        print(''.join(current))
4        return
5
6    for i in range(n):
7        if not used[i]:
8            used[i] = True
9            current.append(items[i])
10            generate(current, used)
11            current.pop()
12            used[i] = False
13
14items = ['A', 'B', 'C']
15n = len(items)
16generate([], [False] * n)

В условии остановки длина текущей последовательности равна \(n\). В цикле рассматриваются все индексы, но выбираются только элементы с признаком \(used[i]=False\). После возврата состояние снова такое же, как перед выбором.

Разобранный пример

Построим все перестановки чисел \(1,2,3\) и проследим первую ветвь. Сначала текущая последовательность пуста. На первом уровне выбирается \(1\), затем \(2\), затем \(3\). Получается \(123\). После печати программа отменяет выбор \(3\), возвращается на деңгей выбора второй позиции и пробует \(3\). Так появляется \(132\).

В задачах может требоваться не печатать варианты, а посчитать подходящие. Тогда в условии остановки проверяют готовую перестановку и увеличивают счётчик, если выполнено требование. Если условие уже нарушено на промежуточном шаге, можно применить правило отсечения ветвей и не продолжать эту ветвь.

Количество вызовов и сложность

В корне дерева есть \(n\) нұсқа выбора, на следующем уровне — \(n-1\), затем \(n-2\) и так далее. Поэтому число листьев равно факториалу \(n!\). Если программа формирует и выводит каждую перестановку целиком, на вывод требуется ещё \(n\) действий для бір листа.

Память для текущей последовательности, массива признаков и стека рекурсивных вызовов составляет \(O(n)\), не считая сохранённых результатов. Глубина рекурсии равна \(n\), то есть используется глубина рекурсии \(n\).

Важные варианты алгоритма

Если элементы могут повторяться, простое хранение индексов приведёт к одинаковым результатам. Например, для букв A, A, B выбор первой и второй A различается в программе, но не различается в строке. Для удаления дублей элементы на каждом уровне перебирают по значениям и не выбирают одинаковое значение дважды.

Другой способ — сначала отсортировать элементы, а затем пропускать повторный выбор одинаковых элементов на одном уровне. Если задача требует перестановки только части элементов, условие остановки меняется: например, при длине \(k\) печатают последовательность, когда \(len(current)=k\), не дожидаясь использования всех \(n\) элементов.

Иногда условие относится к соседним элементам: сумма соседей должна быть чётной, цифры не должны повторяться, запрещены определённые пары. Проверять такие ограничения можно сразу после добавления нового элемента. Это соответствует общей идее отсечения ветвей и уменьшает число вызовов.

Как решать экзаменационную тапсырманы

• Определите, что именно строится: полная перестановка, часть длины \(k\) или перестановка с ограничениями.
• Выберите состояние: текущая последовательность, used и, при необходимости, дополнительные параметры.
• Запишите условие завершения рекурсии.
• Добавьте выбор, рекурсивный вызов и обязательный откат в обратном порядке.
• Проверьте малый пример вручную: для \(n=3\) должно получиться \(6\) нұсқа.
• Оцените число нұсқа и убедитесь, что перебор укладывается в ограничения.

Если задача просит найти количество последовательностей, не обязательно хранить все варианты. Достаточно возвращать число подходящих ветвей или менять общий счётчик. Если нужно найти первый вариант, после успешного результата можно передать сигнал наверх и завершить поиск.

Быстрая проверка