康托展开
康托展开属于组合数学中的一个知识点。用于求出一个排列在全排列中的排名。
时间复杂度
康托展开的时间复杂度是 $O(n^2)$,在用树状数组优化时可以达到 $O(n\ log\ n)$。
实现方法&原理
则有 $ans=a_n\times(n-1)!+a_{n-1}\times(n-2)!+\cdots+a_i\times(i-1)+\cdots+a_1\times0!$
其中,$0\le a_i\le i$,$1\le i\le n$,表示当前数在未出现的元素中排第几个,这就是康托展开。
例如 $3$ 的全排列的康托展开如下:
排列 | 名次 | 康托展开 |
---|---|---|
$1\ 2\ 3$ | $1$ | $0\times2!+0\times1!+0\times0!$ |
$1\ 3\ 2$ | $2$ | $0\times2!+1\times1!+0\times0!$ |
$2\ 1\ 3$ | $3$ | $1\times2!+0\times1!+0\times0!$ |
$2\ 3\ 1$ | $4$ | $1\times2!+1\times1!+0\times0!$ |
$3\ 1\ 2$ | $5$ | $2\times2!+0\times1!+0\times0!$ |
$3\ 2\ 1$ | $6$ | $2\times2!+1\times1!+0\times0!$ |
原理
因为排列是按字典序排名的,因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同,那么如果这一位如果不相同,就按这一位排序。
比如 $4$ 的排列,$[2,3,1,4]<[2,3,4,1]$,因为在第 $3$ 位出现不同,则 $[2,3,1,4]$ 的排名在 $[2,3,4,1]$ 前面。
举个例子
我们知道长为 $5$ 的排列 $[2,5,3,4,1]$ 大于以 $1$ 为第一位的任何排列,以 $1$ 为第一位的 5 的排列有 $4!$ 种。但是我们对第二位的 $5$ 而言,它大于第一位与这个排列相同的,而这一位比 $5$ 小的所有排列。不过我们要注意的是,这一位不仅要比 $5$ 小,还要满足没有在当前排列的前面出现过,不然统计就重复了。因此这一位为 $1$,$3$ 或 $4$,第一位为 $2$ 的所有排列都比它要小,数量为 $3\times3!$。
按照这样统计下去,答案就是 $1+4!+3\times3!+2!+1=46$。注意我们统计的是排名,因此要 $+1$。
代码实现
void cantor()
{
ll ans=1,cnt;
for(ll i=1;i<=n;i++)
{
cnt=0;
for(ll j=i+1;j<=n;j++)
{
if(a[j]<a[i]) cnt++;
}
ans+=cnt*fac[n-i];
}
printf("%lld\n",ans);
}
逆康托展开
康托展开是一个全排列到一个自然数的双射,因此是可逆的。
逆康托展开相当于康托展开逆过来,也就是可以求出某个数某个排名的排列。
实现方法
举个例子,求 $5$ 排名为 $61$ 的排列。以下是逆推过程:
-
$61\div4!=2\cdots13$,说明 $a_5=2$,比首位小的数有 $2$ 个,所以首位为 $3$。
-
$13\div3!=2\cdots1$,说明 $a_4=2$,在第二位之后小于第二位的数有 $2$ 个,所以第二位为 $4$。
-
$1\div2!=0\cdots1$,说明 $a_3=0$,在第三位之后没有小于第三位的数,所以第三位为 $1$。
-
$1\div1!=1\cdots0$,说明 $a_2=1$,在第二位之后小于第四位的数有 $1$ 个,所以第四位为 $5$。
-
最后一位即为剩下的数 $2$。
-
通过以上推导可得所求排列为 $3\ 4\ 1\ 5\ 2$。
代码实现
void decantor(ll num)
{
ll cnt,p;
num--;
for(ll i=1;i<=n;i++) flag[i]=false;
for(ll i=1;i<=n;i++)
{
cnt=num/fac[n-i];
for(p=1;p<=n;p++)
{
if(!flag[p])
{
if(!cnt) break;
cnt--;
}
}
printf("%lld ",p);
flag[p]=true;
num%=fac[n-i];
}
printf("\n");
}