首页 > 专题系列 > 经典问题 > 康拓展开和逆康拓展开的应用
2014
03-07

康拓展开和逆康拓展开的应用

题目:给出n个互不相同的字符并给定它们的相对大小顺序,这样n个字符的所有排列也会有一个顺序.?现在任给一个排列,求出在它后面的第i个排列.这是一个典型的康拓展开应用,首先我们先阐述一下什么是康拓展开。

1)康拓展开

所谓康拓展开是指把一个整数X展开成如下形式:

X=a[n]*(n-1)!+a[n-1]*(n-2)!+…+a[i]*(i-1)!+…+a[2]*1!+a[1]*0!。(其中,a为整数,并且0<=a[i]<i(1<=i<=n)

2)应用实例

{1,2,3,4,…,n}表示1,2,3,…,n的排列如 {1,2,3} 按从小到大排列一共6个:123 132 213 231 312 321。他们间的对应关系可由康托展开来找到。

1324{1,2,3,4}排列数中第几个大的数:

第一位是1小于1的数没有,是0个 0*3! 

第二位是3小于3的数有12,但1已经在第一位了,即1未出现在前面的低位当中,所以只有一个数2 1*2! 

第三位是2小于2的数是1,但1在第一位,即1未出现在前面的低位当中,所以有0个数 0*1! 

所以比1324小的排列有0*3!+1*2!+0*1!=2个,1324是第三个大数。

代码实现:

int kt(int s[],int n)//n表示该排列有n个数
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        int temp = 0;
        for(int j = i + 1; j < n; j++)
          if(s[j] < s[i])
             temp ++;
        sum += f[n - 1 - i] * temp;//f[n]表示n的阶乘
    }
    return sum + 1;
}

 

练习:http://acm.nyist.net/JudgeOnline/problem.php?pid=139

康托展开的逆运算:

{1,2,3,4,5}的全排列已经从小到大排序,要找出第16个数:

1. 首先用16-1得到15

2. 15去除4! 得到015

3. 15去除3! 得到23

4. 3去除2! 得到11

5. 1去除1! 得到10

0个数比它小的数是1

所以第一位是1

2个数比它小的数是3,但1已经在之前出现过了所以是4

1个数比它小的数是2,但1已经在之前出现过了所以是3

1个数比它小的数是2,但1,3,4都出现过了所以是5

最后一个数只能是2

所以这个数是14352

代码实现:

void kt(int sum,int n)
{
    int i, j, s[5];
    bool v[5]={0};
    sum--;
    for(i = 0;i < n; i++)
    {
        int t = sum / f[n - 1 - i];//f[n]表示n的阶乘
        for(j = 0; j < n; j++)
        {
            if(!v[j])
            {
                if(t == 0) break;
                t --;
            }
        }
        s[i] = j;
        v[j] = 1;
        sum %= f[n - 1 - i];
    }
}

练习:http://acm.nyist.net/JudgeOnline/problem.php?pid=143


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。