std::next_permutation Объяснение реализации

Алгоритм std::next_permutation вычисляет следующую лексикографически большую перестановку данной последовательности. Понимание его реализации имеет решающее значение для понимания его поведения.

Схема алгоритма

Алгоритм перебирает последовательность справа налево, отыскивая самый левый «восходящий элемент» (т.е. , элемент, который меньше своего преемника). Если восходящий элемент не найден, это означает, что последовательность находится в порядке убывания, и в этом случае он меняет последовательность, чтобы получить наименьшую перестановку.

В противном случае алгоритм продолжает поиск наименьшего элемента в последовательности справа. зажима (называемого «к»). Затем этот элемент заменяется восходящим элементом. Наконец, элементы справа от восходящего элемента меняются местами, чтобы сохранить порядок убывания.

Роли переменных

• i: Указывает на текущий проверяемый элемент.
• j: Указывает на элемент непосредственно перед i.
• k: Указывает на наименьший элемент в последовательности справа от i, когда я является восходящим элементом.

Поток цикла

Цикл повторяется до тех пор, пока я не достигнет начала последовательности (начала). Внутри каждой итерации:

1. Если i не является восходящим элементом, он уменьшает i и j.
2. Если i является восходящим элементом, он находит наименьший элемент справа от i (k ), меняет его на i и переворачивает все справа от i.

Пример

Рассмотрим последовательность {1, 2, 4, 3} .

• Итерация 1: i изначально находится в позиции 3. j находится в позиции 2. Поскольку 3
• Итерация 2: k оказывается равным 2. 3 заменяется на 2. {1, 3, 4, 2}. Элементы справа от 3 (4 и 2) меняются местами. {1, 3, 2, 4}.
• Итерация 3: i уменьшается, а j уменьшается. i сейчас находится в позиции 2. j находится в позиции 1. 2
• Итерация 4: k оказывается равным 1. 2 заменяется на 1. { 1, 2, 4, 3}. Элементы справа от 2 (4 и 3) меняются местами. {1, 2, 3, 4}.
• Итерация 5: i уменьшается, а j уменьшается. сейчас я на 1. j находится в начале последовательности. Поскольку зажимов больше нет, последовательность обратная. {4, 3, 2, 1}.