一、题目
1、原题链接
排列序数
2、题目描述
如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
⋯ ⋯现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？
输入描述
输入一行，一个串。
输出描述
输出一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。
输入输出样例
输入
bdca
输出
11
二、解题报告
1、思路分析
（1）DFS搜索即可，和全排列数思路一样。
（2）至于序号，与我们搜索到的方案数顺序正好相同，直接将每次搜索到的方案数编号，当时第一思路是将每种方案和其编号记录到哈希表中，之后再进行查找，但是有几个数据超时了（时间复杂度最坏10*10!，超过计算机1s计算量）。可以直接搜到输入的方案直接输出，结束程序即可。
2、时间复杂度
时间复杂度O(n*n!)
3、代码详解
#include <iostream>
#include <string>
using namespace std;
const int N=15;
bool st[N];
string s;
int idx,len;
//DFS搜索，和全排列数的搜索方式相同，只不过参数成了字符串
void dfs(int u,string path){
//如果找到一组方案
if(u==len){
//判断是否和输入的字符串相同
if(path==s){
cout<<idx; //如果相同，直接输出其编号
exit(0); //结束程序
}
idx++;
return ;
}
//搜索，填充每位上的字符
for(int i=0;i<len;i++){
if(!st[i]){ //如果该位的数字没有被用过
char in=char('a'+i),tmp=path[u];
path[u]=in; //将该位置填上数
st[i]=true; //标记为该字母以用过
dfs(u+1,path); //搜索下一个位置
st[i]=false; //回溯
path[u]=tmp; //回溯
}
}
}
int main()
{ cin>>s;
len=s.size(); //记录字符串长度
dfs(0,s); //搜索每种该长度字符串的组合方式
return 0;
}
三、知识风暴
DFS
参考这里
exit(0)：功能—正常运行程序并退出程序，可以用于在非主函数中直接结束程序。
