学步园

康拓展开：

用途：康拓展开主要用于求当前排列在所有排列中排第几（一般从零开始），也可用于搜索标记状态。

公式：ans = a( n ) * ( n - 1) ! + a( n - 1 ) * ( n - 2 ) ! + …… a( i ) * ( i - 1 ) ! +……a2 * 1! + a0 * 0! .( ps: 0! = 1 ) .

公式有了那就剩下求 a( n ) , a( n - 1) , a( n - 2 ) …… 了。先说一下 a( i ) 的意义，a( i ) 代表在 i 之后比 i  小的数的个数。

For example :  s = { 1 , 2 , 3 , 4 }  , 求 s1 = { 3, 2 , 4 , 1 } 在排列中排第几( 按字典序)

                       3 ： 比3小且在3后面的数共有2个  ~> a3=2 ;

                       2 :    比2小且在2后面的数共有1个  ~> a2=1 ;

                       4 :    比4小且在4后面的数共有1个  ~> a1=1 ;

                       1 :    比1小且在1后面的数共有0个   ~> a0=0 ;

so ~ >      ans = 2 * 3! + 1 * 2! + 1 * 1! + 0 * 0! =  15 ( 这里排名从 0 开始 ) ;

再来一个：    s1 = { 2 , 4 , 1 , 3 }  在排列中排第几

                      2 ：  比2小且在2后面的数共有1个 ~> a3 = 1 ; 

                      4 ：  比4小且在4后面的数共有2个 ~> a2 = 2 ;

                      1 ：  比1小且在1后面的数共有0个 ~> a1 = 0 ;

                      3 ：  比3小且在3后面的数共有0个 ~> a0 =0 ;

so ~>   ans = 1 * 3! + 2 * 2! + 0 * 1 ! + 0 * 0! = 10  ;

int cantor(char str[])
{
    int len = strlen(str) ;//计算长度
    int ans = 0 ;
    for(int i=0 ; i<len ; i++)
    {
        int tmp = 0 ;
        for(int j=i+1 ; j<len ; j++)
            if(str[j] < str[i]) tmp++;
        ans += tmp * f[len-i-1];  //f[]为对应阶乘
    }
    return ans ;  //返回该字符串是全排列中第几大
}

逆康拓展开：

用途：很明显与康拓展开相反可以求在序列中第 n 个数的序列。

For example :  序列为  s = { 1 , 2 , 3 , 4 } ,求序列中第排名为10 的序列。

                     1. 用10去除 3！ 商 1 余 4 ;

                     2. 用 4 去除 2！ 商 2 余 0 ;

                     3. 用 0 去除 1！ 商 0 余 0 ;

                     4.  用0 去除 0！ 商 0 余 0 ;

so ~ >   有一个数比第一个数小的是 2 , 有两个数比第二个数小的是 3 ,但是 2 已经在前面出现过，所以这个数为 4 ,有 0 个数比第三个数小的是 1 ,有 0 个数 比第四个数小的数是3 , 所以序列为： s1 = { 2 , 4 , 1 , 3 } .

代码：

void incantor(int n)
{
    memset(vis,false,sizeof(vis)) ;
    for(int i=len-1 ;i>=0 ;i--)
    {
        int j=-1 ;
        for(int k=0 ;k<=n/f[i] ;k++) // f[] 为对应阶乘
            while(vis[++j]) ;
        vis[j]=true ;
        str[len-1-i]='a'+j ;
        a%=f[i] ;
    }
    printf("%s\n",str) ;
}