1.中介数的定义及作用：很多时候，我们要通过一个排列得出它的字典序中的位置（序号），比如1234567应该排在第0位（开始位），1234576应该排在第1位，7654321排在第7！-1=5039位。当然，我们可以通过计算Next_Permutation函数的迭代次数来得到这个数据，但这样时间复杂度最差为O（n!），是非常不划算的，因为我们仅仅要求一个数的位置。所以我们要先从数学的角度去计算这个问题。

3456721排在第几位？1.先看看首位3，在以3开头的数前面有以2开头和以1开头的数，这些数的个数为2*6!个，其中2代表1和2两个数。 2.再看看第二位4。如果已经确定由3开头，那么在4开头前面的数有几种呢？也是以2开头的数和以1开头的所有数，因为3已经放在开头，所以这里不算，这些数的个数为2*5！。3.再往下看，第三位5.如果已经确定34开头，在5开头前面的有几种呢？由于3、4已经放在前面，这里还是只有1、2.这些数的个数为2*4！。4.345已经确定，再6开头的前面有2*3！，再7开头前面有2*2！，在2开头前面有1*1！个（因为只剩1了）,在1开头前面的没有了。（0*0！） 于是我们得到在3456721前面的数有2*6！+2*5！+2*4！+2*3！+2*2！+1*1=1745位。也说是说，在3456721前面的数一共有1745位，由于我们是从0开始的，所以它的位置也就是1745位。 上述计算过程对应了相应的算法：从高位往低位看，或者对于数组而言从序号小的往大的看，按照3，4，5，6，7，2，1[a[0],a[1],a[2],a[3],a[4],a[5],a[6]]的顺序，看它的右边比它小的数的个数k[1],k[2],k[3]...（因为左边的数已经确定了），每一位的k[i]*[(n-i-1)]![此处n=7]乘以它所在的位数-1的阶乘，比如3在第7位（在数组中是第0位，所以用n-0），减1得到后面还剩6位，而k[0]为2，因为在3的右边比3小的数只有两个。其它的位依次类推。为了简化公式，我们一般取i=为数组序号加1（即a[0]我们认为是a[1],用来和实际意义相近，因为我们实际中第一个数都是1而不是C语言中的0）。得到公式：

n-1 

∑  k[i](n-i)! 

i=1

其中i为数组的序号，从1开始，实际写算法时应从0开始，n为数组元素的个数，k[i]表示第i个元素的右边（从第i+1个元素开始到数组末尾）比第i个元素小的元素的个数。 有了上述公式，就可以方便的计算一个排列在字典序中的位置了。比如7654321=6*6！+5*5！+4*4!+3*3!+2*2!+1*1!=5039.到此，我们给出字典序中介数的定义： 定义：由上述算法给出的数组k[i]按照顺序排列所形成的数]1[]...4[]3[]2[]1[nkkkkk叫做这个排列的字典序中介数。如7654321的中介数为654321,3456721的中介数为222221。中介数之所以称为中介数，是因为我们知道一个排列的中介数后，便可以很方便得求得它在字典序中的序号，而这个数在实际上没有明确的意义，所以称为中介数，要注意的是，中介数比原来排列的位数（数组的元素个数）少一位，因为最后一位的结果必然是0。

3.算法代码：

int factorial(int x) { return x > 1 ? x*factorial(x - 1) : 1; }//阶乘
 
 
int* get_permutation_medium(int A[], int n)  //求中介数
{
int* temp = new int[n-1];
 
for (int i = 0; i < n-1; i++)
{
temp[i] = 0;
for (int j = i + 1; j <= n - 1; j++)
{
if (A[j] < A[i])
{
temp[i]++;
}
}
}
return temp;
}
 
int get_permutation_rank(int medium[],int n)   //求第几位
{
int rank = 0;
for (int i = 0; i < n - 1;i++)
{
rank += medium[i]* factorial(n - 1 - i);
}
return rank;
}

外部调用：

int main()
{
int A[] = { 3,4,5,6,7,2,1 };
int n = sizeof(A) / sizeof(A[0]);
int *medium = get_permutation_medium(A, n);
Print(medium, n-1);
int rank =get_permutation_rank(medium, n);
printf("%d\n",rank);
system("pause");
return 0;
}

3.时间复杂度：以上算法的时间复杂度为O（n^2），其中求中介数为O（n^2），由中介数到序号为O（n）。

4.运行截图：

6.参考文档

https://wenku.baidu.com/view/8c79a2facc17552706220880.html