hello-algo/ru/docs/chapter_backtracking/permutations_problem.md

Задача о перестановках

Задача о перестановках является типичным применением алгоритма поиска с возвратом. Она определяется как нахождение всех возможных перестановок элементов заданного множества (например, массива или строки).

В следующей таблице приведены несколько примеров данных, включая входной массив и соответствующие ему перестановки.

Таблица   Примеры перестановок

Входной массив	Все перестановки
[1]	[1]
[1, 2]	[1, 2], [2, 1]
[1, 2, 3]	[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

Случай без повторяющихся элементов

!!! question

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

С точки зрения алгоритма поиска с возвратом, мы можем представить процесс генерации перестановок как результат серии выборов. Предположим, входной массив — [1, 2, 3]. Если мы сначала выберем 1, затем выберем 3 и, наконец, выберем 2, то получим перестановку [1, 3, 2]. Возврат означает отмену выбора с последующей попыткой других вариантов.

С точки зрения кода поиска с возвратом, множество кандидатов choices — это все элементы входного массива, а состояние state — это элементы, выбранные на данный момент. Обратите внимание, что каждый элемент может быть выбран только один раз, поэтому все элементы в state должны быть уникальными.

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

Обрезка повторного выбора

Чтобы реализовать выбор каждого элемента только один раз, мы рассмотрим введение булевого массива selected, где selected[i] указывает, был ли уже выбран choices[i], и на его основе реализуем следующую операцию обрезки.

• После выбора choice[i] мы присваиваем selected[i] значение \text{True}, что означает, что элемент уже выбран.
• При переборе списка выборов choices пропускаем все уже выбранные узлы, то есть выполняем обрезку.

Как показано на рисунке ниже, предположим, что в первом раунде мы выбираем 1, во втором раунде выбираем 3, в третьем раунде выбираем 2. Тогда необходимо во втором раунде обрезать ветвь элемента 1, а в третьем раунде обрезать ветви элементов 1 и 3.

Наблюдая за рисунком выше, можно заметить, что эта операция обрезки уменьшает размер пространства поиска с O(n^n) до O(n!).

Реализация кода

После понимания вышеизложенной информации мы можем заполнить пробелы в каркасе кода. Чтобы сократить общий код, мы не будем реализовывать отдельные функции из каркаса, а развернем их в функции backtrack():

[file]{permutations_i}-[class]{}-[func]{permutations_i}

Случай с повторяющимися элементами

!!! question

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

Предположим, входной массив — [1, 1, 2]. Для удобства различения двух повторяющихся элементов 1 обозначим второй 1 как \hat{1}.

Как показано на рисунке ниже, описанный выше метод генерирует перестановки, половина из которых является дубликатами.

Как же удалить повторяющиеся перестановки? Наиболее прямой способ — использовать хеш-множество для прямого удаления дубликатов из результатов перестановок. Однако это не очень элегантно, поскольку ветви поиска, генерирующие повторяющиеся перестановки, не нужны и должны быть заранее идентифицированы и обрезаны, что может дополнительно повысить эффективность алгоритма.

Обрезка одинаковых элементов

Наблюдая за рисунком ниже, в первом раунде выбор 1 или выбор \hat{1} эквивалентны, и все перестановки, сгенерированные при этих двух выборах, будут дубликатами. Поэтому следует обрезать \hat{1}.

Аналогично, после выбора 2 в первом раунде, во втором раунде выбора 1 и \hat{1} также создадут повторяющиеся ветви, поэтому \hat{1} во втором раунде также следует обрезать.

По сути, наша цель — обеспечить, чтобы в каждом раунде выбора несколько одинаковых элементов выбирались только один раз.

Реализация кода

На основе кода из предыдущей задачи мы рассмотрим открытие хеш-множества duplicated в каждом раунде выбора для записи элементов, которые уже были опробованы в этом раунде, и обрежем повторяющиеся элементы:

[file]{permutations_ii}-[class]{}-[func]{permutations_ii}

Предположим, что элементы попарно различны, тогда n элементов имеют n! перестановок (факториал); при записи результата необходимо скопировать список длиной n, что занимает O(n) времени. Следовательно, временная сложность составляет $O(n!n)$.

Максимальная глубина рекурсии равна n, используется O(n) пространства стека. selected использует O(n) пространства. В один момент времени максимум существует n множеств duplicated, использующих O(n^2) пространства. Следовательно, пространственная сложность составляет $O(n^2)$.

Сравнение двух типов обрезки

Обратите внимание, что хотя selected и duplicated используются для обрезки, их цели различны.

• Обрезка повторного выбора: во всем процессе поиска существует только один selected. Он записывает, какие элементы содержатся в текущем состоянии, и его роль заключается в предотвращении повторного появления элемента в state.
• Обрезка одинаковых элементов: каждый раунд выбора (каждая вызванная функция backtrack) содержит один duplicated. Он записывает, какие элементы уже были выбраны в текущем раунде обхода (цикл for), и его роль заключается в обеспечении того, чтобы одинаковые элементы выбирались только один раз.

На рисунке ниже показана область действия двух условий обрезки. Обратите внимание, что каждый узел в дереве представляет выбор, а путь от корневого узла к листовому узлу через различные узлы образует перестановку.