《算法分析设计与综合实践》实验报告
学生姓名：曹晨学号：171310402指导教师：章昭辉
请勿转载或抄袭
n个元素{1，2，，n}有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，，n!-1。每个排列的序号为其字典序值。例如n=3时，6个不同排列的字典序值如下：
字典序值
0
1
2
3
4
5
排列
123
132
213
231
312
321
数据输入：
输入的第一行是元素的个数n。接下来的1行是n个元素{1，2，，n}的一个排列
结果输出：
输出的第一行是字典序值，第二行是按字典序排列的下一个排列
设给定的{1，2，，n}的排列为π，其字典序值为rank(π,n)。按字典序的定义显然有：
以π[1]开头的第一个排列(π[1]-1)(n-1)!<=rank(π,n)<=π[1](n-1)!-1。以π[1]开头的最后一排列
这是什么意思呢？明白意思就要先搞明白π[1]代表什么，前面条件告诉我们，π是一个排列，那么π[1]就是这个排列第一个元素的值，π[i]就是第i个元素的值（这个我想了一晚上才反应过来），假如π="26458173"的话，那么π[1]=2，π[2]=6,π[3]=4等。
最主要的思想来了，也是我没有想到的：设r是π在以π[1]开头的所有排列中的序号，则r也是{π[2]，π[3]，，π[n]}作为集合{1，2，，n}-{π[1]}（减去π[1]）中排列的的字典序值。如果将{π[2]，π[3]，，π[n]}中每个大于π[1]的元素都减去1，则得到集合{1，2，，n-1}的一个排列π''，其字典序值也是r。由此得到计算rank(π,n)的递归式如下：
rank(π,n)=(π[1]-1)(n-1)!+rank(π'',n-1)
初始条件为rank(π[1],1)=0
26458173
(2-1)*7!
6458173->5347162
5347162
(5-1)*6!
347162->346152
346152
(3-1)*5!
46152->35142
35142
(3-1)*4!
5142->4132
4132
(4-1)*3!
132->132
(1-1)*2!
32->21
21
(2-1)*1!
1->1
(1-1)*0!
(2-1)*7!+(5-1)*6!+(3-1)*5!+(3-1)*4!+(4-1)*3!+(1-1)*2!+(2-1)1*1!+(1-1)*0!=8227
对于每个整数r，0<=r<=n!-1，都有唯一的阶层分解：r=∑di*i!(0<=di<=i，1<=i<=n-1)。
设r=rank(π,n)，则π[1]=dn-1+1，进而由r''=r-dn-1(n-1)!=rank(π'',n-1)可递归找到排列π''。
r=dn-1*(n-1)!++d2*2!+d1*1!+d0*0!
先得到尾项再得到前项，因为(r%1!)=0，任意的d0=(r%1)/0!=0，所以初始条件为1
r=8228
d=(r%2!)/1!=0
b[6]=1
大于b[i]的已经出现的都要加1，和上面的减1对称
12
r=8288
d=(r%3!)/2!=1
b[5]=2
r=8226
d=(r%4!)/3!=3
b[4]=4
4213
r=8202
d=(r%5!)/4!=2
b[3]=3
35214
r=8160
d=(r%6!)/5!=2
b[2]=3
346215
r=7290
d=(r%7!)/6!=4
b[1]=5
5347216
r=5040
d=(r%8!)/7!=1
b[0]=2
26458317
附录：（要求代码里各行要有注释）
用自己的思想编写的代码（利用next_permutation库函数）
intfactorial(intn)
{
if(n==1)
return1;
elsereturnn*factorial(n-1);
}//用于计算n的阶乘
voidfindSum(int*a,intn)
intcount=0;
intsum=0;//该排列的字典序值
for(inti=0;i for(intj=i+1;j if(a[i]>a[j]) count++;//用来表示第i位的后面比它小的数的个数 } sum+=count*factorial(n-i-1);//加上这一位前面的排序数 count=0; cout< intmain() intn;//元素的个数 cin>>n; inta[n]; for(inti=0;i cin>>a[i]; }//数组用来存放元素 findSum(a,n);//调用计算字典序值的函数 if(next_permutation(a,a+n))//调用计算下一个排列的库函数 cout< }//输出下一个排列 return0; 用（参考答案和csdn上的思想）自己编写的代码： //计算n的阶乘 elseif(n==0) //由排序计算字典序值 intpermRank(intn,int*a){ intr=0;//字典序值初始化 inti; intb[n]; for(i=0;i b[i]=a[i]; }//把元素放进数组b中 for(i=0;i r+=(b[i]-1)*factorial(n-i-1);//加上当前阶层的字典序值 if(b[i] b[j]--; }//改变后段的值,把比当前的值大的值减1 returnr;//返回字典序值 //由字典序值计算排列 voidpermUnrank(intn,intr,int*b) if(n>=factorial(n)) return;//如果n的数值大于排列的最大序值，则无输出 b[n-1]=1;//初始化最后一位数为1 for(intj=1;j intd=(r%factorial(j+1))/factorial(j);//求当前阶层的d r-=d*factorial(j);//总值减去这一阶层的值 b[n-1-j]=d+1;//当前位的值等于d+1 for(inti=n-1-j+1;i if(b[i]>d)//可以改为if(b[i]>=b[n-1-j]) b[i]++; }//这个for循环是用来把大于等于当前位且已存在的值加1 cout< }//输出排序 return; //由排列计算下一个排列 voidpermSucc(intn,int*a,int&flag) inti=n-2;//从最后一个开始往前遍历 while(a[i+1] i--; }//直到遇到前面一个的值小于后面一个的值时停止 if(i==-1) flag=0;//flag等于0意味着a的排列时所有排列中的最后一个，即逆序，没有下一个排列了