康拓逆展开

以你之姓@ 2022-06-17 08:41 183阅读 0赞

康托展开的逆运算：  
  
\{1,2,3,4,5\}的全排列已经从小到大排序，要找出第16个数：  
  
1. 首先用16-1得到15  
  
2. 用15去除4! 得到0余15  
  
3. 用15去除3! 得到2余3  
  
4. 用3去除2! 得到1余1  
  
5. 用1去除1! 得到1余0  
  
有0个数比它小的数是1  
  
所以第一位是1  
  
有2个数比它小的数是3，但1已经在之前出现过了所以是4  
  
有1个数比它小的数是2，但1已经在之前出现过了所以是3  
  
有1个数比它小的数是2，但1,3,4都出现过了所以是5  
  
最后一个数只能是2

所以这个数是14352

前提是在它后面的数，意思就是它前面比它小的不算进去

#include<cstdio>
    #include<algorithm>
    using namespace std;
    int f[10]={1,1,2,6,24,120,720,5040,40320,362880};
    int s[10];
    void kt(int sum,int n)
    {
        int i,j;
        bool v[10]={0};
        sum--;
        for(i = 0;i < n; i++)
        {
    	//得到有t个数比它小(数的范围是1到n),假设t=0，那就是在1 到 n 中 有 0个数比它小的，那这个数（即它） 只能是1了，因为只有 1 有0个数比它小；
            int t = sum / f[n - 1 - i];
            for(j = 1; j <=n; j++)//这个从小到大的for就巧妙了，从小到大数t个数，就可以得到 满足条件的那个数（这里的条件是指 ：有t个数比它小）
              {
                if(!v[j])//这里就是那个前提,他前面比它小的不算
                {
                    if(t == 0)
                    break;
                    t--;
                }
            }
            s[i] = j;//j就是找到的，最后把s这个数组全部输出就是要求的排列
            v[j] = 1;
    	
            sum %= f[n - 1 - i];
        }
    }
    int main()
    {
        int n,m;
        while(~scanf("%d %d",&n,&m))
        {
        kt(n,m);
        for(int i=0;i<m;i++)
            printf("%d",s[i]);
        printf("\n");
        }
        return 0;
    }