做TC练习的时候,学习高手的代码,看到了这个神器。用于生成不重复的且不小于当前排列的全排列。

next_permutation

function fun.cpp
1
2
3
4
5
6
7
 template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last );

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 lexicographically next greater permutation of elements. The comparisons of individual elements are performed using either operator< for the first version, or comp for the second.

A permutation 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 on 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.

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), 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. comp Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument is to be considered less than the second argument.

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

next_permutation tset.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  cout << "The 3! possible permutations with 3 elements:\n";

  sort (myints,myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while ( next_permutation (myints,myints+3) );

  return 0;
}

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

注意

当输出{1, 1, 1}的全排列时只输出一组“1 1 1”;

上升全排列

int myints[] = {1,2,3}; 输出为:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

int myints[] = {3,2,1}; 输出为:
3 2 1

int myints[] = {2,3,1}; 输出为:
2 3 1
3 1 2
3 2 1

所以想得到给定数组元素的全排列,首先要sort为单调上升序列。

Complexity

At most, performs one half as many swaps as the number of elements in the range.