問題描述：
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
方案一：
使用STL函數
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
const int INF=1<<30;
char a[31],b[31];
int main()
{
int n,i,k;
while (~scanf("%d",&n))
{
for (i=0;i<n;i++)
{
getchar();
scanf("%c",&a[i]);
}
for (i=0;i<n;i++)
b[i]=i+'1';
int cnt=0;
do{
if (cnt==k+1)
{
for (i=0;i<n;i++)
printf("%c ",b[i]);
printf("\n");
break;
}
if (strcmp(a,b)==0)
{
k=cnt;
printf("%d\n",k);
}
cnt++;
}while (next_permutation(b,b+n));
}
return 0;
}
方法二：
根據排列
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define ll long long
const int INF=0x7fffffff;
const int N=1000+2;
int a[11],b[11],c[11],vis[11],d[11],n;
/*a數組用來儲存階乘，b輸出用來儲存輸入資料，
c數組用來儲存符合條件的數量，vis數組用來記錄是否被通路
d數組用來存儲下一個排列*/
void init()
{
int i;
a[0]=a[1]=1;
for (i=2;i<11;i++)
a[i]=i*a[i-1];
}
int main()
{
int i,j;
init();
while (~scanf("%d",&n))
{
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
int cnt=0;
for (i=1;i<=n;i++)
{
scanf("%d",&b[i]);
vis[b[i]]=1;
for (j=b[i]-1;j>0;j--)
if (vis[j]==0)
c[i]++;
cnt+=c[i]*a[n-i];
}
printf("%d\n",cnt);
cnt++;
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
d[0]=0;
for (i=1;i<=n;i++)
{
j=0;
while (c[i]<cnt/a[n-i]+1)
{
if (vis[j]==0)
c[i]++;
j++;
} //兩個while就是為了尋找下個數字，可能不太好看，也不高效，
while (vis[j]==1) //但現在有點暈，先湊合着吧，以後再改改
j++;
d[i]=j;
cnt%=a[n-i];
vis[d[i]]=1;
}
for (i=1;i<=n;i++)
printf("%d ",d[i]);
printf("\n");
}
return 0;
}