康拓展开&&逆康拓展开

康拓展开：

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

公式：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(string str){
     
    
   

    

     

    
    

     
   int ans = 0 ;
     
    
   

    

     

    
    

     
   for(int i = 0 ;i < str.length() ; ++i){
     
    
   

    

     

    
    

     
 int temp = 0 ;
     
    
   

    

     

    
    

     
 for(int j = i+1 ;j < str.length() ; ++j)
     
    
   

    

     

    
    

     
 if(str[i] > str[j])
     
    
   

    

     

    
    

     

       temp++ ;
     
    
   

    

     

    
    

     

       ans += temp * f[str.length()-i-1] ;
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     
   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

                     第二个数: 它后面有两个数比它小，如果2不被确定为第一个数，那么这个数一定是3，因为2已经被确定为第一个数了，所以这个数就是4了

                     第三个数: 它后面有0个数比它小，那么第三个数就是1

                     第四个数: 它后面有0个数比它小，那么第三个数就是4

              所以序列为： s1 = { 2 , 4 , 1 , 3 } .

代码：

  

   

    

     

    
    

     

      string Incantor(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 string str="" ;
     
    
   

    

     

    
    

     
 int len = 4 ;
     
    
   

    

     

    
    

     
 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 +=('1'+j) ;
     
    
   

    

     

    
    

     

       n%=f[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return str ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/25068965