C++ STL next_permutation()函数算法实现

1. next_permutation()函数

next_permutation函数原型为：

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

该函数的功能是按照词典（或Compare comp函数）确定的顺序在原容器内生成[first, last)序列的下一个排列。如果下一个排列存在，函数将通过迭代器完成顺序调整，且返回值为true；否则，序列变为初始序列并且返回值为false。

比如：如果迭代器指向字符串“abcd”，经过next_permutation将返回true，并在原容器内给出“abdc”字符串。

next_permutation()函数在文字处理中非常实用。探究其算法原理也有助于我们加深对文字处理的理解。

2. next_permutation算法

实际上可以认为next_permutation截取的是全排列中的一个时刻。首先看看我们在做全排列时是怎么做的，有助于我们找到next_permutation的算法核心。比如，给定数字{1,2,3,4}，下面按照顺序写出其全排列（数字无重用）：

1234 //初始排列
1243 //交换3和4
1324 //交换2和3，并且重排3之后数字顺序
1342 //交换2和4
1423 //交换3和4，并且重排4之后数字顺序
1432 //交换2和3
2134 //交换1和2，并且重排2之后数字顺序
2143 //交换3和4
2314 //交换1和3，并且重排3之后数字顺序
2341 //交换1和4
2413 //交换3和4，并重排4之后数字顺序
2431 //交换1和3
3124 //交换2和3，并重排3之后数字顺序
3142 //交换2和4
3214 //交换1和2，并重排2之后数字顺序
3241 //交换1和4
3412 //交换2和4，并重排4之后数字顺序
3421 //交换1和2
4123 //交换3和4，并重排4之后数字顺序
4132 //交换2和3
4213 //交换1和2，并重排2之后数字顺序
4231 //交换1和3
4312 //交换2和3，并重排3之后数字顺序
4321 //交换1和2

总结上面的方法，我们在初始排列的基础上，每次从排列尾端着手，试图找到一对数字(i, j)，满足条件{(i, j) | i<j}，并交换其位置；有时候满足条件的数字对很多，我们总是按照以下顺序来操作：
1）比较最后两个数字，若满足，直接交换；
2）不满足，把排在前面一个数字纳入进来，分别用后面的数字与其比较（按照从后往前的顺序逐个比较，顺序很重要！），若有数字对满足要求，直接交换，然后前一个数字之后的所有数字排序；
3）如此循环往复，直到再也找不到一个数字比其后面的数字小，排列结束。

注意交换后的排序，其实在完成交换之后，前一个交换点以后的数字是按照降序排列的（否则之前就会发现一个逆序对满足条件{(i, j) | i<j}），因此排序只需要将前一个交换点之后的序列调转顺序（reverse函数），而不需要用sort函数。

上述算法其实就是next_permutation的算法，区别仅在于next_permutation只需找到下一个排列，而不用遍历所有排列。

下面以程序来实现。

3. 程序

template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
  BidirectionalIterator front = last - 1;
  BidirectionalIterator rear = last - 1;
  bool found = false;
  BidirectionalIterator i;
  while (!found && front > first)
  {
    i = rear; 
    front--;
    while(i>front)
    {
      if (comp(*front, *i))
      {
        found = true;
        break;
      }
      else
        i--;
     }
   }
   if (found)
   {
     swap(*i, *front);
     reverse(front + 1, last);
     return true;
  }
  else
  {
    reverse(first, last);
    return false;
  }
}

int main()
{ 
  string str = "1234";
  int i = 1;
  cout << i << ":" << str << endl;
  while (next_permutation(str.begin(), str.end(), less<char>()))
  {
    i++;
    cout << i << ":" << str << endl;
  }
}

输出：

4. 结束语

prev_permutation()函数的作用和next_permutation()函数正相反，但是其算法原理是相同的。在STL next_permutation()函数第二个原型中，如将Compare comp函数设置为greater函数，其起到的作用其实就是prev_permutation()的功能。有兴趣的读者可以自行一试。

原文链接：https://blog.csdn.net/weixin_45845093/article/details/102934449