目录

一， 前一个排列（字典序更大的最近的一个排列）

 1.1 底层实现

      1.2  prev_permulation()

 二，下一个排列（字典序更小的最近的一个排列）

        1.1 底层实现 

     1.2   next_permulation()

三，全排列

四，元素想等的排列

---

 

一， 前一个排列（字典序更大的最近的一个排列）

 1.1 底层实现

#include<bits/stdc++.h>
using namespace std;const int maxn=103;int n,a[maxn];int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);int pos,sw;for(pos=n-1;pos>=1;--pos){if(a[pos]>a[pos+1])break;}for(sw=pos+1;sw<=n;++sw){if(a[sw]>a[pos])break;}--sw;// printf("%d %d !\n",pos,sw);swap(a[pos],a[sw]);sort(a+pos+1,a+n+1,greater<int>());for(int i=1;i<=n;++i)printf("%d ",a[i]);puts("");return 0;
}

      1.2  prev_permulation()

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;int a[105];for (int i = 0; i < n; i++){cin >> a[i];}prev_permutation(a, a + n);for (int i = 0; i < n; i++){cout<< a[i]<<" ";}return 0;
}

 二，下一个排列（字典序更小的最近的一个排列）

        1.1 底层实现 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;const int maxn = 103;int n, a[maxn];int main() {cin >> n;for (int i = 1; i <= n; ++i) cin>>a[i];int pos, sw;for (pos = n - 1; pos >= 1; --pos) {if (a[pos] < a[pos + 1])break;//与prev_permulation不同的地方 > 变 <}for (sw = pos + 1; sw <= n; ++sw) {if (a[sw] < a[pos])break;//与prev_permulation不同的地方 > 变 <}--sw;// printf("%d %d !\n",pos,sw);swap(a[pos], a[sw]);sort(a + pos + 1, a + n + 1, greater<int>());for (int i = 1; i <= n; ++i)printf("%d ", a[i]);puts("");return 0;
}

     1.2   next_permulation()

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;int a[105];for (int i = 0; i < n; i++){cin >> a[i];}next_permutation(a, a + n);for (int i = 0; i < n; i++){cout<< a[i]<<" ";}return 0;
}

 

三，全排列

        全排列没有现成的函数，我们可以利用 next_permulation() 获得。

1.先将字符串从小到大排序

2.用 do~while 循环，使用next_permultion() 不断获取下一个排列（字典序更小的排列）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;int a[105], b[105];for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n);do {for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;} while (next_permutation(a, a + n));return 0;
}

四，元素想等的排列

         is_permutation（），只要元素相同就返回 true ，而不管顺序是否相同

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;int a[105],b[105];for (int i = 0; i < n; i++){cin >> a[i];b[i] = a[i];}next_permutation(a, a + n);cout << "a :" << endl;for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;cout << "b :" << endl;for (int i = 0; i < n; i++){cout << b[i] << " ";}cout << endl;if (is_permutation(a, a + n,b, b + n)){cout << "a 与 b 相等\n";}else{cout << "a 与 b 不相等\n";}return 0;
}