std:: next_permutation
Rearranges the elements in the range [first,last) into the next lexicographically greater permutation.
A is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographicaly to each other; The first such-sorted possible permutation (the one that would compare lexicographically smaller to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.
The comparisons of individual elements are performed using either operator< for the first version, or comp for the second.
If the function can determine the next higher permutation, it rearranges the elements as such and returns true . If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false .
Parameters
first, last Bidirectional iterators to the initial and final positions of the sequence. The range used is [first,last) , which contains all the elements between first and last , including the element pointed by first but not the element pointed by last .
BidirectionalIterator shall point to a type for which swap is properly defined.
comp Binary function that accepts two arguments of the type pointed by BidirectionalIterator , and returns a value convertible to bool . The value returned indicates whether the first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.
Return value
true if the function could rearrange the object as a lexicographicaly greater permutation.
Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// next_permutation example // std::cout // std::next_permutation, std::sort int main () < int myints[] = ; std::sort (myints,myints+3); std::cout "The 3! possible permutations with 3 elements:\n"; do < std::cout << myints[0] ' ' << myints[1] ' ' << myints[2] '\n'; > while ( std::next_permutation(myints,myints+3) ); std::cout "After loop: " << myints[0] ' ' << myints[1] ' ' << myints[2] '\n'; return 0; >The 3! possible permutations with 3 elements: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 After loop: 1 2 3
Complexity
Up to linear in half the distance between first and last (in terms of actual swaps).
Data races
The objects in the range [first,last) are modified.
Exceptions
Throws if any element swap throws or if any operation on an iterator throws.
Note that invalid arguments cause undefined behavior.
See also
prev_permutation Transform range to previous permutation (function template) lexicographical_compare Lexicographical less-than comparison (function template)
Алгоритмы стандартной библиотеки C++
Заголовочный файл algorithm содержит много полезных алгоритмов.
Большинство из этих алгоритмов принимают в качестве параметра два итератора, будем обозначать их first и last. В этом случае алгоритм работает с элементами контейнера от first включительно до last невключительно. Чаще всего в качестве first используется метод begin(), а в качестве last — метод end(), в этом случае алгоритм применяется ко всему контейнеру. Например,
Используя операции «+» и «-» для итераторов можно применять алгоритмы не для всего контейнера, а для части.
Можно передавать также reverse_iteraror, наиболее употребительный способ использования — это сортировка в обратном порядке при помощи:
Алгоритмы поиска
find
Алгоритм find(first, last, val) осуществляет линейный поиск значения val от итератора first до итератора last . Элементы просматриваются последовательность, возвращается итератор на первый найденный элемент. Если элемент val не будет найден, то возвращается значение итератора last .
binary_search
Алгоритм binary_search(first, last, val) осуществляет двоичный поиск значения val . Контейнер должен быть упорядочен. Возвращается значение типа bool , то есть true или false в зависимости от того, есть ли такой элемент в контейнере.
lower_bound
Алгоритм lower_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который не меньше, чем val , то есть *res>=val , a *(res-1)
upper_bound
Алгоритм upper_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который строго больше, чем val , то есть *res>val , a *(res-1)
Алгоритмы сортировки, разворота, сдвига
sort
sort(first, last) — упорядочивает элементы контейнера по неубыванию.
stable_sort
sort(first, last) — упорядочивает элементы контейнера по неубыванию, при этом равные элементы не переставляются (так называемая «устойчивая сортировка»).
reverse
reverse(first, last) — разворачивает фрагмент контейнера в обратном порядке, переставляя элементы, равноудаленные от концов.
rotate
reverse(first, n_first, last) — осуществляет циклический сдвиг фрагмента контейнера. Элемент, на который указывает итератор n_first становится первым элементом (то есть переходит на место элемента first ), элемент n_first+1 — вторым и т.д.
Перестановки
next_permutation
next_permutation(first, last) — переставляет элементы так, чтобы получилась следующая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true , если удалось построить следующую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была максимальной в лексикографическом порядке, то метод генерирует минимальную в лексикографическом порядке перестановку и возвращает false .
Например, вывести все перестановки в лексикографическом порядке можно так:
prev_permutation
prev_permutation(first, last) — переставляет элементы так, чтобы получилась предыдущая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true , если удалось построить предыдущую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была минимальной в лексикографическом порядке, то метод генерирует максимальную в лексикографическом порядке перестановку и возвращает false .
random_shuffle
random_shuffle(first, last) — делает случайную перестановку элементов контейнера.
Минимальные и максимальные элементы, подсчет
min_element
Алгоритм min_element(first, last) находит минимальный элемент в контейнере и возвращает итератор на этот элемент. Если есть несколько элементов, равных минимальному, возвращается значение первого из них.
max_element
max_element(first, last) возвращает итератор на наибольший элемент. Если есть несколько элементов, равных наибольшему — то на первый из них.
count
count(first, last, val) — подсчитывает сколько элементов контейнера равны значению val .
C++ Algorithm next_permutation ()
C++ Algorithm next_permutation() function is used to reorder the elements in the range [first, last) into the next lexicographically greater permutation.
A permutation is specified as each of several possible ways in which a set or number of things can be ordered or arranged. It is denoted as N! where N = number of elements in the range.
Syntax
Parameter
first: A bidirectional iterator pointing to the first element in the range to be permuted.
last: An input iterator pointing the position one past the last in the range to be permuted.
comp: A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order, otherwise returns false. It follows the strict weak ordering to order the elements.
Return value
It returns true if the function could reorder the object as a lexicographically greater permutations.
Else, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).
Complexity
Complexity is up to linear in half the distance between first and last.
Data Races
The objects in the range [first, last) are modified.
Exceptions
This function throws an exception if either element are swapped or an operation on iterator throws an exception.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let’s see the simple example to demonstrate the use of next_permutation():
Output:
aab aba baa
Example 2
Let’s see another simple example:
Output:
The 3! possible permutations with 3 elements: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 After loop: 1 2 3
Example 3
Let’s see another simple example:
Output:
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
Example 4
Let’s see a simple example:
Output:
231 312 321
Next Topic C++ Algorithm
For Videos Join Our Youtube Channel: Join Now
Feedback
- Send your Feedback to [email protected]
Help Others, Please Share
Learn Latest Tutorials
Python Design Patterns
Preparation
Trending Technologies
B.Tech / MCA
Javatpoint Services
JavaTpoint offers too many high quality services. Mail us on h[email protected], to get more information about given services.
- Website Designing
- Website Development
- Java Development
- PHP Development
- WordPress
- Graphic Designing
- Logo
- Digital Marketing
- On Page and Off Page SEO
- PPC
- Content Development
- Corporate Training
- Classroom and Online Training
- Data Entry
Training For College Campus
JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected].
Duration: 1 week to 2 week
Like/Subscribe us for latest updates or newsletter 
Как работает next_permutation в С++?
Кто в курсе, можете рассказать, как работает next_permutation в С++? Зачем этой функции нужны два итератора? Где она хранит состояние между вызовами. Сейчас пилил just for fun такую штуку на шарпе и стало интересно.
beaver ☆
04.10.19 17:00:36 MSK
Meyer ★★★★★
( 04.10.19 17:14:42 MSK )
Последнее исправление: Meyer 04.10.19 17:16:42 MSK (всего исправлений: 1)
Ну так скачайте исходники gcc и найдите там как реализовано, в отличии от всяких там непосредственно кодов компилятора, исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.
p.s. кодю на C++ уже как 3-й год наверное, в т.ч. по основной работе, активно юзаю STL, а о такой штуке как next_permutation даже и не слышал 🙂
bonta ★★★★★
( 04.10.19 17:15:05 MSK )
Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator
А в этом случае состояние описывается упорядоченностью элементов и хранить отдельно его не нужно.
GPFault ★★
( 04.10.19 20:15:14 MSK )
Ответ на: комментарий от bonta 04.10.19 17:15:05 MSK
исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.
Вот совсем нет. Стиль оформления кода у них настолько чудовищный, что исходники читаются только чуть лучше, чем никак.
m0rph ★★★★★
( 04.10.19 20:28:05 MSK )
Ответ на: комментарий от GPFault 04.10.19 20:15:14 MSK
Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator
Я только пытаюсь понять функцию, но на cppreference пример переставляет строку std::sort(«aba») :
aab aba baa