Hi, I’m Lin.

I write program.

利用cantor展开按顺序打印m到n的全排列

cantor展开

cantor展开是一个很好的hash方法，[1,n]的n个不相同的连续数，每一种排列都对应有它的顺序。
比如说{1,2,3}里面，123，132，213，231，312，321分别是他们在按照十进制从小到大排列，一共3!种。
如果按照直接hash的方法，{1,2,3}至少要开321大小的数组，利用cantor展开则可以减少到6。

考虑3124在{1,2,3,4}中的位置：
第一位是3，比3小的数有2个，因此比3124小的至少有 2*3!
第二位是1，比1小的数有0个，因此比3123小的至少有 2*3! + 0*2!
第三位是2, 比2小的数有1个，但是因为1已经被前面的位使用了，当前值不变 2*3! + 0*2! + 0*1! 到最后一位的时候除了最后的值其他的数都已经被使用掉了，所以不必考虑。
然后我们就可以得到3124在{1,2,3,4}中排第12位

cantor展开得到原来的数

根据第几位打印cantor展开前的数。思路其实就是cantor展开的逆方向。

按顺序打印m到n的全排列

打印全排列的直接想法就是递归。SICP里面好像就有这个练习，但是使用cantor展开更符合人的思维啊。
其实说完cantor展开接下来就没有什么好说的了，循环1到n!,每个调用一遍cantor_reverse就好了。
如果是m到n嘛，修改一下cantor_reverse函数就好了。
PS. 我是标题党

贴一下打印1到n全排列的代码

#include <cstdio>

void cal_fac();
unsigned long cantor(unsigned long S);
unsigned long cantor_reverse(unsigned long X);

int main(int argc, const char *argv[])
{
    cal_fac();
    for(int i=0;i<24;i++)
        printf("%lu\n",cantor_reverse(i));
    return 0;
}

int fac[12];
const int cantor_len = 4;
void cal_fac()
{
    fac[1] = 1;
    for(int i=2;i<=cantor_len-1;i++)
        fac[i] = i*fac[i-1];
}
// 4321:0   1234:23
unsigned long cantor(unsigned long S)
{
    unsigned long x=0;
    bool hash[cantor_len+1] = {0};
    for(int i=cantor_len;i>=2;i--)
    {
        int k = S%10;
        S /= 10;
        hash[k] = true;
        k--;
        for(int j=k;j>=1;j--)
            if(hash[j]) k--;
        x += fac[i-1]*k;
    }
    return x;
}

unsigned long cantor_reverse(unsigned long X)
{
   unsigned long base = 1, s = 0;
   bool hash[cantor_len+1] = {0};
   for(int i=cantor_len-1;i>=1;i--)
   {
       int k = X / fac[i] + 1;
       for(int j=1;j<=k;j++)
           if(hash[j]) k++;
       hash[k] = true;
       s += k * base;
       base *= 10;
       X %= fac[i];
   }
   for(int i=1;i<=cantor_len;i++)
       if(!hash[i])
       {
           s += i * base;
           break;
       }
   return s;
}