Перебор всех перестановок
Материал из Algocode wiki
Версия от 13: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