std::next_permutation

default (1)	template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
custom (2)	template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

default (1)

template <class BidirectionalIterator>  bool next_permutation (BidirectionalIterator first,                         BidirectionalIterator last);

custom (2)

template <class BidirectionalIterator, class Compare>  bool next_permutation (BidirectionalIterator first,                         BidirectionalIterator last, Compare comp);

Transform range to next permutation

Rearranges the elements in the range[first,last) into the nextlexicographically greater permutation.

Apermutation is each one of theN! possible arrangements the elements can take (whereN is the number of elements in the range). Different permutations can be ordered according to how they comparelexicographicaly to each other; The first such-sorted possible permutation (the one that would comparelexicographically 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 eitheroperator< for the first version, orcomp for the second.

If the function can determine the next higher permutation, it rearranges the elements as such and returnstrue. 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 returnsfalse.

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 betweenfirst andlast, including the element pointed byfirst but not the element pointed bylast.
BidirectionalIterator shall point to a type for whichswap is properly defined.
comp: Binary function that accepts two arguments of the type pointed byBidirectionalIterator, and returns a value convertible tobool. The value returned indicates whether the first argument is considered to go before the second in the specificstrict 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 returnsfalse to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

Example

// next_permutation example#include <iostream>// std::cout#include <algorithm>// std::next_permutation, std::sortint main () {int myints[] = {1,2,3};  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;}

Output:

The 3! possible permutations with 3 elements:1 2 31 3 22 1 32 3 13 1 23 2 1After loop: 1 2 3

Complexity

Up to linear in half thedistance betweenfirst andlast (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 causeundefined behavior.

Movatterモバイル変換

C++

Reference

C library:

Containers:

Input/Output:

Multi-threading:

Other:

<algorithm>