CKTIS / C++
std::next_permutation — следваща лексикографска пермутация
std::next_permutation пренарежда диапазон до следващата му лексикографска пермутация. Връща true, ако има следваща; след последната възстановява първото подреждане и връща false.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
template<class BidirectionalIterator>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);std::next_permutation от <algorithm> променя диапазона [first, last) на място. Лексикографският ред на две подреждания се определя от първата позиция, на която елементите им не са еквивалентни според използваното сравнение. Вариантът без comp използва сравнението по подразбиране „по-малко от“; вариантът с comp определя реда чрез този компаратор.
Резултат true означава, че е намерено следващо подреждане. Резултат false не означава, че данните са останали непроменени: алгоритъмът възстановява първото подреждане, сортирано във възходящ ред според използваното сравнение. За празен диапазон или диапазон с един елемент функцията връща false.
Итераторите трябва да са двупосочни, а елементите, към които сочат, трябва да позволяват разместване на стойности. comp трябва да дефинира строг слаб ред; не използвайте <=. За N елемента стандартът ограничава броя на разместванията до N / 2.
Започнете с диапазон, сортиран според същото сравнение, и използвайте do–while, за да обработите и началното подреждане. Цикълът обхожда по едно подреждане за всяка различна последователност от класове на еквивалентност, определени от сравнението. Ако сравнението третира различни стойности като еквивалентни, цикълът може да пропусне някои различни последователности от стойности. В примера сравнението по подразбиране разграничава 1 от 2, затова цикълът извежда и трите различни подреждания на стойностите. Примерът показва и състоянието след последното извикване, което връща false.
Примери
#include <algorithm>
#include <array>
#include <iostream>
int main() {
std::array<int, 3> values{1, 1, 2};
do {
std::cout << values[0] << ' ' << values[1] << ' '
<< values[2] << '\n';
} while (std::next_permutation(values.begin(), values.end()));
std::cout << "reset: " << values[0] << ' ' << values[1]
<< ' ' << values[2] << '\n';
}
Резултат
1 1 2 1 2 1 2 1 1 reset: 1 1 2
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.