Перебор всех перестановок

Материал из Algocode wiki
Версия от 16:26, 6 февраля 2021; Глеб (обсуждение | вклад) (Новая страница: «=Задача= Перебрать все перестановки в лексикографическом порядке =Код= <syntaxhighlight lang="C++">...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Перебрать все перестановки в лексикографическом порядке

Код

int perm[MAXN];
bool used[MAXN];
void gen(int cur_index) {
  if (cur_index == n) {
    //получена перестановка
  } else {
    for (int i = 1; i <= n; i++) {
     if (!used[i]) {
        used[i] = 1;
        perm[cur_index] = i;
        used[i] = 0;
     }
  }
}

Важное уточнение

В с++ существует функция next_permutation, которая генерируют следующую перестановку, следовательно для того чтобы сгенерировать следующую перестановку мы просто можем ее использовать, пока не найдем последнюю перестановку.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin