排列的字典序问题Permrank题解

时间:2023-02-05 00:18:43

先附上n=4的时候的4*3!=24种情况

1 23 4     1 2 4 3     1 3 2 4    1 3 4 2     1 4 2 3     1 4 3 2

2 13 4     2 1 4 3     2 3 1 4    2 3 4 1     2 4 1 3     2 4 3 1

3 12 4     3 1 4 2     3 2 1 4    3 2 4 1     3 4 1 2     3 4 2 1

4 12 3     4 1 3 2     4 2 1 3    4 2 3 1     4 3 1 2     4 3 2 1

这里现注意第一点,1 2 3 4序号为0,4 3 2 1的序号为15

不需要全排列出来然后一个一个判断,那样可能会爆时间,这里有个更好的规律方法

这里举个2 3 4 1的例子

1 23 4     1 2 4 3     1 3 2 4    1 3 4 2     1 4 2 3     1 4 3 2

2 13 4     2 1 4 3     2 3 1 4    2 3 4 1     2 4 1 3    2 4 3 1

3 12 4     3 1 4 2     3 2 1 4    3 2 4 1     3 4 1 2     3 4 2 1

4 12 3     4 1 3 2     4 2 1 3    4 2 3 1     4 3 1 2     4 3 2 1

“2  3  4  1”从前往后循环,现写出2 3 4 1的序号:

 

2 3 4 1=(2-1)*3!+(2-1)*2! +(2-1)*1! +1 -1=6+2+1+1-1=9

 

从第一位2开始循环,判断第a[i]位在i后面所有的数中大了多少个,像2在后面是大了一个自己是第二个(倒数第几,这种意思只可意会不可言传=  =),然后(2-1)。其实这个a[i]大了后面1个就是(2-1)=1这个1,这两个意思是一样的。思路是一样的

例如这个2,(2-1)*3!就是6,就除去了所有1开头的6个数!!保留了其他的。

这样实质就是每次减去一种情况,再减去一种情况......就留下来了我们所需要的第几位数

但是可以优化:

for (int f=1;f<=x-1;f++)

              if (a[z]>a[f]) y - -;

从前往后面找,比如2 3 4 1 中的3,从第一位找到i-1位,只要比a[i]小,那么就y - -,这样子就求出来了ronaldo函数+1的值。

这里用一个函数来求ronaldo(鄙人喜欢C罗CristianoRonaldo)

sum+=ronaldo(i,a[i],i)*j[i-1]

这里j[i]是阶乘,因为考试时候这道题范围是n<=13;这就是专门

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[14],j[15]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
int n,sum=0;
int ronaldo(int x,int y,int z)
{
if (x==1) return a[x]-1;
if (x==n) return 1;
for (int f=1;f<=x-1;f++)
if (a[z]>a[f]) y--;
return y-1;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
sum=sum+ronaldo(i,a[i],i)*j[n-i];
cout<<sum-1<<endl;//因为从0开始算第一个
next_permutation(a+1,a+n+1);
for (int i=0;i<=n-1;i++)
cout<<a[i]<<" ";
}

给我打表用的- -

然后由上述式子循环一遍后输出sum-1  因为第一个序号为0

最后用next_permutation(a,a+n)  这里不知道怎么从1开始,所以我的数组从1开始只好向前推一位,然后用next_permutation(a,a+n);这个函数很强大的

                                                                                                  By   Carry