全排列

STL

发布日期: 2021-01-31

阅读次数:

函数排序 next_permutation() prev_permutation()

注意事项

函数next_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次增大直至到最大字典序
函数prev_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次减小直至到最小字典序
即二者排序方式是完全相反的，前者按照升序进行排列，后者按照降序进行排列
（此方法不光可应用于整型，字符型可是可以的）

介绍

存在于头文件中，有如下代码

int a[];
do
{

}
while(next_permutation(a,a+n));

具体使用

输入n，产生1~n的全排列

#include <iostream>
#include <algorithm>
  using namespace std;
  int main(){
      int n;
      cin>>n;
          int a[1000];
        //这里输入的是需要进行排列的元素，若需要排列1~n，只需依次给a[i]赋值即可 
          for(int i=0;i<n;i++)  
              cin>>a[i];

         //sort(a,a+n);  如果是a[i]已经按照从小到大的顺序赋值的话，则可以不用sort
         do{
             for(int i=0;i<n;i++)
                 cout<<a[i];
             cout<<endl;
         }while(next_permutation(a,a+n));  
         //next_permutation(a,a+n),有下一个排序就返回true，否走返回false 

     return 0;
}

例如输入
3
1 0 2

如果有sort() //即是按照从从小到大的顺序
输出为

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

若无
则输出为

1 0 2
1 2 0
2 0 1
2 1 0

补充

若a[3]={1,2,3}
如果改成 while(next_permutation(a,a+2));（只对前两个元素进行字典排序）
则输出：
1 2 3
2 1 3

显然，如果改成 while(next_permutation(a,a+1));
则只输出：1 2 3

若int a[3]={3,2,1};
next_permutation(a,a+3);
则只输出：3 2 1

常规回溯做法

Code

#include<iostream>
using namespace std;

int p[10]={0};
bool vis[10]={0};
int n;

void dfs(int x)
{    
    if (x==n+1){
        for(int i=1;i<=n;i++)
        cout<<p[i]<<" ";
        cout<<endl;
        return;
    }
    for (int i=1;i<=n;i++){
        if (vis[i]==false){
            p[x] = i;
            vis[i] = true;
            dfs(x+1);   //没达到n，继续加1 
            vis[i] = false; //回溯清空当前状态，将vis[i]设为没访问过 
        }
    }
}

int main()
{
    while (cin>>n){
        dfs(1);
    }
    return 0;
}