全排列

· · 个人记录

next\_permutation函数

其实就是算从 [1-n] 的所有数的全部的排列可能情况

先看代码

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

这个代码输出的为

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

可以看出，为全排列

当把 next\_permutation(num,num+3) 改为 num+2,输出就变为了

1 2 3

2 1 3

只针对前两位进行全排列

由此可以看出，next\_permutation(num,num+n) 函数是对数组 num 中的前 n 个元素进行全排列，同时并改变 num 数组的值。

另外，需要强调的是，next\_permutation() 在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。

2.运用

```cpp int cmp(char a,char b) { if(tolower(a)!=tolower(b))//tolower 是将大写字母转化为小写字母. return tolower(a)<tolower(b); else return a<b; } . . . while(next_permutation(ch,ch+strlen(ch),cmp)); ``` ### 下面是一道例题： **[ABC183 $Travel$](https://atcoder.jp/contests/abc183/tasks/abc183_c)** **题意：** 有 $N$ 个城市，从城市 $i$ 到城市 $j$ 需要的时间记为 $T_{i,j}$。 问从城市 $1$ 出发，经过所有的其他城市，再回到城市 $1$，而且每个城市只能走一次。求需要时间正好为 $K$ 的线路个数。 **解法：** 根据数据范围，我们可以很轻松的进行全部枚举。 因此，这道题的做法很明显是对地图中数组进行全排列，在枚举过程中，记录当前已经用的时间 $sum$，如果 $sum=k$ ,答案就 $+1$ 。 **代码：** ```cpp int n,k,mp[10][10],a[10]; int main(){ cin>>n>>k; for(int i=1;i <= n;i++) for(int j=1;j <= n;j++) cin>>mp[i][j]; for(int i=1;i <= n;i++) a[i]=i; a[n+1]= 1;//让最后一个城市回到城市1 int ans=0, sum=0; do{ sum=0; for(int i=1;i<=n+1;i++) sum += mp[a[i-1]][a[i]]; if(sum==k) ans++; } while(next_permutation(a+2,a+n+1));//c++的全排列函数，注意要从第二个城市开始 cout<<ans<<endl; return 0; } ```