标题:排列序数
如果用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
再例如:
输入:
cedab
程序应该输出:
70
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
如果用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
再例如:
输入:
cedab
程序应该输出:
70
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。
分析:将输入的字符串进行全排列,按字典序进行排序编号并存在string型数组中,然后遍历string数组,相同则输出该数组的下标即可。
代码:
#include <iostream>#include <algorithm>
#include <string>
#include <string.h>
char ch[15];
using namespace std;
int f(int x)//求阶乘
{
if(x==1)
return 1;
return f(x-1)*x;
}
string a[3700000];//10的阶乘为3628800
int main()
{
cin>>ch;
string q=(string)ch;
int len=strlen(ch);
int maxx=f(len);//最大编号
//cout<<len<<' '<<maxx<<endl;
int i=0;
sort(ch,ch+len);//重要!!!
do
{
a[i++]=(string)ch;
}while(next_permutation(ch,ch+len));
for(int j=0;j<maxx;j++)
{
if(a[j]==q)
{
cout<<j;
return 0;
}
}
return 0;
}
样例数据:
边界数据:
思路二:只需要遍历字符串中的每一个字符,然后找出每个字符后面有多少个比它小的,也就是逆序的,然后乘以后面字符个数的阶乘,每一步的结果相加即可。
#include<iostream>#include<cstring>using namespace std;int a[20];int main(){ a[1]=1; for(int i=2;i<13;i++) { a[i]=a[i-1]*i; } char str[15]; cin>>str; int len=strlen(str),index=0,num; for(int i=0;i<len;i++) { num=0; for(int j=i+1;j<len;j++) { if(str[j]<str[i]) { num++; } } index+=num*a[len-1-i]; } cout<<index<<endl; return 0;}
第二种解法更好一点。