STL のマニュアルより Next_permutation is an overloaded name; there are actually two next_permutation functions. template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); template <class BidirectionalIterator, class StrictWeakOrdering> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp); Description †Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements. There is a finite number of distinct permutations (at most N! [1], where N is last - first), so, if the permutations are ordered by lexicographical_compare, there is an unambiguous definition of which permutation is lexicographically next. If such a permutation exists, next_permutation transforms [first, last) into that permutation and returns true. Otherwise it transforms [first, last) into the lexicographically smallest permutation [2] and returns false. The postcondition is that the new permutation of elements is lexicographically greater than the old (as determined by lexicographical_compare) if and only if the return value is true. The two versions of next_permutation differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp. Definition †Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. Requirements on types †For the first version, the one that takes two arguments:
The ordering relation on BidirectionalIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements. For the second version, the one that takes three arguments:
Preconditions †[first, last) is a valid range. Complexity †Linear. At most (last - first) / 2 swaps. Example †This example uses next_permutation to implement the worst known deterministic sorting algorithm. Most sorting algorithms are O(N log(N)), and even bubble sort is only O(N^2). This algorithm is actually O(N!). template <class BidirectionalIterator> void snail_sort(BidirectionalIterator first, BidirectionalIterator last) { while (next_permutation(first, last)) {} } int main() { int A[] = {8, 3, 6, 1, 2, 5, 7, 4}; const int N = sizeof(A) / sizeof(int); snail_sort(A, A+N); copy(A, A+N, ostream_iterator<int>(cout, "\n")); } Notes †
|