<<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以及n个元素{1,2,?, n }的一个排列，计算出这个排列的字典序值，以及按字典 序排列的下一个排列。
数据输入： 输出元素个数n。接下来的1 行是n个元素 {1,2,……, n }的一个排列。
结果输出: 将计算出的排列的字典序值和按字典序排列的下一个排列输出。第一行是字典序值，第2行是按字典序排列的下一个排列。
Sample Input
8 2 6 4 5 8 1 7 3
Sample Output
8227
2 6 4 5 8 3 1 7
分两步：
一、计算字典值。
看例子：
tot=0；
比2小的数有1个，则 tot+=1*7！；
比6小的数有4个，则 tot+=4*6！；
比4小的数有2个，则 tot+=2*5！；
比5小的数有2个，则 tot+=2*4！；
比8小的数有3个，则 tot+=3*3！；
比1小的数有0个，则 tot+=0*2！；
比7小的数有1个，则 tot+=1*1！；
比3小的数没有；
（注：在排列中，求比某个数小的数的个数时，排除之前出现过的数）
参考资料：http://blog.csdn.net/designer_/article/details/5478250
二、下一个排列。
从数组尾部开始找相邻两个元素，满足order[i]<order[i+1]，再从数组尾部开始找第一个大于order[i]的数order[k]（k>i），交换order[i]和order[k]，order[i+1]~order[n-1]进行逆向重排。
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 void myswap(int * a, int * b) 5 { 6 long long t; 7 t = *a; 8 *a = *b; 9 *b = t; 10 } 11 12 int main() 13 { 14 int n,i,k,j,t,order[100]; 15 int lis,f[100],mid,h; 16 f[0]=1; 17 for(i=1;i<=22;i++) 18 f[i]=f[i-1]*i; 19 while(scanf("%d",&n)!=EOF) 20 { 21 for(i=0;i<n;i++) 22 scanf("%d",&order[i]); 23 if(n==1) 24 printf("0\n"); //此时下一个排列不存在 25 else if(n>=2) 26 { 27 lis=0; 28 for(i=0,k=n-1;i<n-1;i++,k--) 29 { 30 t=0; 31 for(j=0;j<i;j++) 32 if(order[j]<order[i]) t++; 33 lis+=(order[i]-1-t)*f[k]; 34 } 35 printf("%d/n",lis); 36 37 //求下一个排列时可以直接把数组初始化为给定的序列调用一次next_permutation即可 38 for(i=n-2; i>=0; i--) 39 { 40 if(order[i] < order[i+1]) 41 { 42 j = i; 43 for(k=n-1; k>j; k--) 44 { 45 if(order[k] > order[j]) 46 { 47 mid = j+(n-j)/2; 48 myswap(&order[j], &order[k]); 49 for(j++, h = 1; j <= mid; j++, h++) 50 myswap(&order[j], &order[n-h]); 51 } 52 } 53 break; 54 } 55 } 56 for(i=0; i < n-1; i++) 57 printf("%d ",order[i]); 58 printf("%d\n",order[i]); 59 } 60 } 61 return 0; 62 }
