next_permutation

2023-11-20 20:07:40

STL 概述

该函数的作用是用来求解一组序列的下一个排列，这里的下一个排列并不是随机的序列，而是在能组合的所有序列中次大于当前序列的序列。

这样说可能比较绕口，就是 abc 的下一个序列为 acb，1 2 3 的下一个序列为 1 3 2。

函数原型

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

next_permutation 能算出 [first,last) 这个序列的下一个序列，若存在则返回 true，否则返回 false。

使用样例

1. 整数序列

1.1 整数数组

  #include <bits/stdc++.h>
  using namespace std;
  int a[3]={1,2,3};
  int main()
  {
      do{
          for (auto x : a) cout << x << ' ';
          cout << endl;
      }while(next_permutation(a,a+3));
      return 0;
  }

1.2 vector

#include <bits/stdc++.h>
using namespace std;
vector<int> v = {1,2,3};
int main()
{
    do{
        for (auto x : v) cout << x << ' ';
        cout << endl;
    }while(next_permutation(v.begin(),v.end()));
    return 0;
}

它们的输出结果都为:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

2. 字符序列

2.1 字符数组

#include <bits/stdc++.h>
using namespace std;
char c[3] = {'a','b','c'};
int main()
{
    do{
        for (auto x : c) cout << x << ' ';
        cout << endl;
    }while(next_permutation(c,c+3));
    return 0;
}

2.2 String

#include <bits/stdc++.h>
using namespace std;
string s = "abc";
int main()
{
    do{
        cout << s << endl;
    }while(next_permutation(s.begin(),s.end()));
    return 0;
}