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

Что такое перестановка?

Перестановка — это способ расставить все n элементов в некотором порядке.

есть n разных элементов
нужно расположить их в каком-то порядке

Например, для чисел:

1 2 3

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

В перестановках порядок важен. Поэтому 1 2 3 и 3 2 1 — разные перестановки.

Сколько всего перестановок?

Если все элементы разные, то количество перестановок равно:

n!

Факториал:

n! = 1 * 2 * 3 * ... * n

Например:

3! = 1 * 2 * 3 = 6

Поэтому у чисел 1, 2, 3 есть 6 перестановок.

Почему n!?

Для первой позиции можно выбрать любой из n элементов.

Для второй позиции остается n - 1 элементов. Для третьей — n - 2.

n вариантов для первой позиции
n - 1 вариантов для второй
n - 2 вариантов для третьей
...
1 вариант для последней

Поэтому:

n * (n - 1) * (n - 2) * ... * 1 = n!

Перестановки, сочетания, размещения

Тип	Что значит	Порядок важен?
Перестановки	Расставить все n элементов	Да
Сочетания	Выбрать k из n	Нет
Размещения	Выбрать k из n и расставить	Да

Задача генерации

Дано число n. Нужно вывести все перестановки чисел от 1 до n.

Input

Output

Идея генерации через рекурсию

Будем строить перестановку слева направо.

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

cur — текущая перестановка
used[x] — использовали ли число x
если cur.size() == n, выводим cur

Код: генерация перестановок

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> cur;
vector<int> used;

void gen() {
    if ((int)cur.size() == n) {
        for (int x : cur) {
            cout << x << ' ';
        }

        cout << '\n';
        return;
    }

    for (int x = 1; x <= n; x++) {
        if (used[x]) {
            continue;
        }

        used[x] = 1;
        cur.push_back(x);

        gen();

        cur.pop_back();
        used[x] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    used.assign(n + 1, 0);

    gen();

    return 0;
}

Как работает рекурсия?

Для n = 3:

сначала выбираем первое число
потом второе
потом третье
когда длина стала 3, выводим перестановку

Например:

cur = []
берем 1 → cur = [1]
берем 2 → cur = [1, 2]
берем 3 → cur = [1, 2, 3]
выводим 1 2 3

Потом делаем откат:

убираем 3
убираем 2
пробуем другое число

Что такое backtracking?

Backtracking — это метод, где мы:

1. делаем выбор
2. идем глубже рекурсией
3. откатываем выбор
4. пробуем следующий вариант

В коде это выглядит так:

used[x] = 1;
cur.push_back(x);

gen();

cur.pop_back();
used[x] = 0;

Если забыть pop_back или used[x] = 0, генерация сломается.

Генерация через next_permutation

В C++ есть готовая функция:

next_permutation

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

Нужно начать с отсортированного массива:

1 2 3 ... n

Код: next_permutation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }

    do {
        for (int x : a) {
            cout << x << ' ';
        }

        cout << '\n';
    } while (next_permutation(a.begin(), a.end()));

    return 0;
}

Лексикографический порядок

Лексикографический порядок — это порядок как в словаре.

Для перестановок чисел:

Это именно тот порядок, который дает next_permutation, если начать с отсортированного массива.

prev_permutation

Есть и обратная функция:

prev_permutation

Она строит предыдущую перестановку. Для нее нужно начать с убывающего массива.

vector<int> a = {3, 2, 1};

do {
    for (int x : a) {
        cout << x << ' ';
    }

    cout << '\n';
} while (prev_permutation(a.begin(), a.end()));

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

Перестановки можно генерировать не только для чисел, но и для строки.

string s;
cin >> s;

sort(s.begin(), s.end());

do {
    cout << s << '\n';
} while (next_permutation(s.begin(), s.end()));

Например:

abc

Даст:

abc
acb
bac
bca
cab
cba

Если есть одинаковые элементы

Если в массиве есть одинаковые элементы, то next_permutation не будет выводить одинаковые перестановки повторно.

Например, строка:

aab

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

aab
aba
baa

Но важно сначала отсортировать:

sort(s.begin(), s.end());

Код: уникальные перестановки строки

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    sort(s.begin(), s.end());

    do {
        cout << s << '\n';
    } while (next_permutation(s.begin(), s.end()));

    return 0;
}

Количество перестановок с повторами

Если элементы повторяются, количество уникальных перестановок меньше.

Формула:

n! / (c1! * c2! * ... * ck!)

Где c1, c2, ... — количества одинаковых элементов.

Например:

aab

Здесь:

n = 3
a встречается 2 раза
b встречается 1 раз

Количество:

3! / 2! = 3

Номер перестановки

Иногда нужно найти номер перестановки в лексикографическом порядке.

Например:

Перестановка 2 3 1 имеет номер 4.

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

Смотрим слева направо. На каждой позиции считаем, сколько меньших неиспользованных чисел можно поставить.

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

количество таких перестановок = cnt * factorial[remaining]

Код: номер перестановки

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> p(n);

    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    vector<long long> fact(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
    }

    vector<int> used(n + 1, 0);

    long long rank = 1;

    for (int i = 0; i < n; i++) {
        int cnt = 0;

        for (int x = 1; x < p[i]; x++) {
            if (!used[x]) {
                cnt++;
            }
        }

        rank += cnt * fact[n - i - 1];
        used[p[i]] = 1;
    }

    cout << rank;

    return 0;
}

Этот код использует 1-indexed номер: первая перестановка имеет номер 1.

Перестановка по номеру

Обратная задача: дано n и номер k. Нужно найти k-ю перестановку в лексикографическом порядке.

Идея:

на первой позиции каждая группа имеет размер (n-1)!
по k понимаем, какой элемент поставить первым
потом переходим к следующей позиции

Код: перестановка по номеру

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long k;

    cin >> n >> k;

    vector<long long> fact(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
    }

    vector<int> nums;

    for (int i = 1; i <= n; i++) {
        nums.push_back(i);
    }

    k--;

    vector<int> ans;

    for (int pos = 0; pos < n; pos++) {
        long long block = fact[n - pos - 1];
        long long id = k / block;

        ans.push_back(nums[id]);

        nums.erase(nums.begin() + id);

        k %= block;
    }

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Здесь k тоже 1-indexed. Если k = 1, получим первую перестановку.

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

Input

3 4

Output

2 3 1

Потому что:

Проверка, является ли массив перестановкой

Иногда нужно проверить, что массив длины n является перестановкой чисел от 1 до n.

То есть каждое число от 1 до n встречается ровно один раз.

vector<int> cnt(n + 1, 0);

for (int x : a) {
    if (x < 1 || x > n) {
        cout << "NO";
        return 0;
    }

    cnt[x]++;
}

for (int x = 1; x <= n; x++) {
    if (cnt[x] != 1) {
        cout << "NO";
        return 0;
    }
}

cout << "YES";

Полный код проверки

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> cnt(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> a[i];

        if (a[i] < 1 || a[i] > n) {
            cout << "NO";
            return 0;
        }

        cnt[a[i]]++;
    }

    for (int x = 1; x <= n; x++) {
        if (cnt[x] != 1) {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";

    return 0;
}

Циклы в перестановке

Перестановку можно рассматривать как отображение:

i → p[i]

Тогда элементы разбиваются на циклы.

Например:

p = [2, 3, 1, 5, 4]

Циклы:

1 → 2 → 3 → 1
4 → 5 → 4

Код: разложение на циклы

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> p(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    vector<int> used(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            int v = i;

            while (!used[v]) {
                used[v] = 1;
                cout << v << ' ';
                v = p[v];
            }

            cout << '\n';
        }
    }

    return 0;
}

Асимптотика

Метод	Время	Память
Генерация всех перестановок	O(n! * n)	O(n)
next_permutation	O(n! * n)	O(n)
Номер перестановки	O(n²)	O(n)
Перестановка по номеру	O(n²)	O(n)
Проверка перестановки	O(n)	O(n)
Разложение на циклы	O(n)	O(n)

Перестановок очень много. Уже при n = 10 количество перестановок равно 3628800.

Когда какой способ использовать?

Задача	Способ
Вывести все перестановки	Рекурсия или next_permutation
Нужен лексикографический порядок	next_permutation
Нужно генерировать вручную	Backtracking
Найти номер перестановки	Факториалы и used
Найти перестановку по номеру	Факториальная система
Проверить массив	cnt или used

Типичные ошибки

Забыть, что порядок в перестановках важен
Не сделать used[x] = 0 после рекурсии
Не сделать cur.pop_back() после рекурсии
Запустить next_permutation не с отсортированного массива
Получить overflow в факториалах
Перепутать 0-indexed и 1-indexed номер перестановки
Думать, что генерация перестановок работает быстро для больших n
Не учитывать одинаковые элементы в строке

Короткий шаблон генерации

int n;
vector<int> cur;
vector<int> used;

void gen() {
    if ((int)cur.size() == n) {
        for (int x : cur) {
            cout << x << ' ';
        }

        cout << '\n';
        return;
    }

    for (int x = 1; x <= n; x++) {
        if (used[x]) {
            continue;
        }

        used[x] = 1;
        cur.push_back(x);

        gen();

        cur.pop_back();
        used[x] = 0;
    }
}

Короткий шаблон next_permutation

vector<int> a(n);

for (int i = 0; i < n; i++) {
    a[i] = i + 1;
}

do {
    for (int x : a) {
        cout << x << ' ';
    }

    cout << '\n';
} while (next_permutation(a.begin(), a.end()));

Главное запомнить

перестановка = расстановка всех n элементов
порядок важен
количество перестановок = n!
генерировать можно рекурсией или next_permutation
для больших n все перестановки вывести невозможно