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

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

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

<p align="center"> Таблица <id> &nbsp; Примеры перестановок </p>

| Входной массив | Все перестановки                                                    |
| :------------- | :------------------------------------------------------------------ |
| $[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`. Начиная с корневого узла, после трех раундов выбора мы достигаем листовых узлов, каждый из которых соответствует одной перестановке.

![Рекурсивное дерево для полных перестановок](../assets/permutations_i.png)

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

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

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

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

![Пример обрезки при полных перестановках](../assets/permutations_i_pruning.png)

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

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

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

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

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

!!! question

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

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

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

![Повторяющиеся перестановки](../assets/permutations_ii.png)

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

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

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

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

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

![Обрезка повторяющихся перестановок](../assets/permutations_ii_pruning.png)

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

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

```src
[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`), и его роль заключается в обеспечении того, чтобы одинаковые элементы выбирались только один раз.

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

![Область действия двух условий обрезки](../assets/permutations_ii_pruning_summary.png)