Перейти к содержанию

5.2 Генерация перестановок

Теперь рассмотрим задачу генерации всех перестановок множества из n элементов. Например, для множества {0,1,2} все перестановки таковы:

(0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1) и (2,1,0).

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

Метод 1

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

Ниже приведена типичная реализация для множества {0,1,...,n-1}. Вектор permutation хранит текущую перестановку, а массив chosen показывает, какие элементы уже взяты.

void search() {
    if (permutation.size() == n) {
        // обработать перестановку
    } else {
        for (int i = 0; i < n; i++) {
            if (chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

Как это работает

Каждый рекурсивный вызов добавляет в текущую перестановку ещё один элемент. Если длина permutation стала равной n, это означает, что очередная перестановка уже полностью построена.

Допустим, мы хотим сгенерировать перестановки множества {0,1,2,3}. Тогда работа алгоритма выглядит так:

  • сначала выбирается первый элемент;
  • затем из оставшихся выбирается второй;
  • потом третий;
  • и, наконец, четвёртый.

Например, одна из ветвей рекурсии может быть такой:

  • берём 2,
  • затем 0,
  • затем 3,
  • затем 1.

В результате получается перестановка (2,0,3,1).

flowchart TD
    A["start: []"]

    A --> B["взять 0"]
    B --> C["взять 1 → [0,1]"]
    C --> D["взять 2 → [0,1,2]"]
    B --> E["взять 2 → [0,2]"]
    E --> F["взять 1 → [0,2,1]"]

    A --> G["взять 1"]
    G --> H["взять 0 → [1,0]"]
    H --> I["взять 2 → [1,0,2]"]
    G --> J["взять 2 → [1,2]"]
    J --> K["взять 0 → [1,2,0]"]

    A --> L["взять 2"]
    L --> M["взять 0 → [2,0]"]
    M --> N["взять 1 → [2,0,1]"]
    L --> O["взять 1 → [2,1]"]
    O --> P["взять 0 → [2,1,0]"]
Hold "Ctrl" to enable pan & zoom

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

Почему метод корректен

Алгоритм рассматривает каждый элемент как возможного кандидата на очередную позицию и никогда не использует один и тот же элемент дважды. Значит:

  • каждая построенная последовательность действительно является перестановкой;
  • каждая возможная перестановка будет построена ровно один раз.

Оценка сложности

Всего у множества из n элементов имеется n! перестановок. Следовательно, если мы хотим перебрать их все, время работы не может быть лучше этого порядка. Рекурсивный алгоритм работает за O(n!) перестановок, а если учитывать обработку каждой перестановки как массива длины n, то обычно говорят о O(n · n!).

Метод 2

Есть и другой способ: начать с перестановки

{0,1,...,n-1}

и затем многократно строить следующую перестановку в возрастающем лексикографическом порядке.

В C++ для этого есть готовая функция next_permutation.

vector<int> permutation;

for (int i = 0; i < n; i++) {
    permutation.push_back(i);
}

do {
    // обработать перестановку
} while (next_permutation(permutation.begin(), permutation.end()));

Что делает next_permutation

Функция преобразует текущую перестановку в следующую по лексикографическому порядку. Например, если начать с последовательности:

[1,2,3]

то далее будут получены:

[1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

После последней перестановки функция вернёт false, и цикл завершится.

Небольшой пример

Пусть n = 3. Тогда алгоритм последовательно переберёт:

  1. [0,1,2]
  2. [0,2,1]
  3. [1,0,2]
  4. [1,2,0]
  5. [2,0,1]
  6. [2,1,0]

Это все возможные перестановки без пропусков и повторов.

Когда этот способ особенно удобен

Такой подход хорош, когда:

  • не хочется писать рекурсивный код;
  • нужно просто пройти по всем перестановкам;
  • удобно работать именно в лексикографическом порядке.

На практике next_permutation часто оказывается самым коротким и аккуратным решением.

Сравнение двух подходов

Оба метода генерируют все перестановки, но делают это по-разному.

Рекурсивный способ:

  • даёт больше контроля;
  • легко модифицируется под задачи с ограничениями;
  • хорошо подходит как база для более сложного поиска.

Итеративный способ через next_permutation:

  • короче в реализации;
  • удобен для полного перебора;
  • особенно хорош, если перестановки уже нужно получать в отсортированном порядке.

Идея, которую важно запомнить

Генерация перестановок — это фундаментальный инструмент полного перебора. Если число элементов маленькое, можно перебрать все варианты и среди них выбрать лучший, посчитать количество подходящих или проверить существование нужной конфигурации.

Но важно помнить, что число перестановок растёт очень быстро:

  • 3! = 6
  • 5! = 120
  • 8! = 40320
  • 10! = 3628800

Поэтому полный перебор перестановок применим только тогда, когда n достаточно мало.

Подведем черту

Для генерации перестановок чаще всего используют два метода:

  1. Рекурсию с массивом использованных элементов — более гибкий способ.
  2. next_permutation — более компактный и практичный способ в C++.

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