康托展开和逆康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

解决的问题类型：有一组元素，按字典序从小排到大，在所有的组合类型中，某个组合排第几？(从0开始排，或者说比该组合小的组合个数有多少）

公式：康托展开值x = a[n-1]*(n-1)! + a[n-2]*(n-2)! + ...... + a[i]*i! + ......+ a[1]*1! + a[0]*0! ;

a[i]为整数,表示当前未出现的元素排第几个（从0开始排，或者说比该元素小的元素个数）。

举例说明，有{1，2，3，4，5} 5个元素。按字典序排列，最小的排列组合是12345，最大的排列组合是54321，计算34152的康托展开值。n=5。

第一位是3，3在未出现的元素12345这5个元素中排第3，但是从0开始排，a[4]=2;

第二位是4，4在未出现的元素1245中排第3(3已经出现过了)从0开始排，a[3]=2;

第三位是1，1在未出现的元素125中排第1(3和4已经出现过了)，从0开始排，a[2]=0;

第四位是5，在未出现的元素25中，比5小的元素有1个，a[1]=1;

第五位是2，在未出现的元素2中，比2小的元素有0个，a[0]=0;

x = a[4]*4! + a[3]*3! + a[2]*2! + a[1]*1! + a[0]*0!

x = 2*4! + 2*3! + 0*2! + 1*1! +0*0! = 61

按照正常人的逻辑，从0开始排，排到61，就是所谓的62。

逆康托展开：求在所有全排列中排在第x位的组合是什么？

举例说明，在{1,2,3,4,5}的排列组合中，排在第62位的是多少？

62-1=61。n=5，从(n-1)的阶乘(n-1)!开始除。

61 / 4! = 2......13,说明a[4]=2，在所有未出现的元素12345中比首位小的数有2个，显然是3

13 / 3! = 2......1,说明a[3]=2,在所有未出现的元素1245中比第二位小的数有2个，显然是4

1 / 2! = 0......1,说明a[2]=0,在所有未出现的元素125中比第三位小的数有0个，显然是1

1 / 1！= 1......0,说明a[1]=1,在所有未出现的元素25中比第四位小的数有1个，显然是5

最后一个，a[0]=0,最后一个就是2了

所以排列组合是34152。

139-我排第几个

内存限制:64MB 时间限制:1000ms
难度:3

题目描述:

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

输入描述:

第一行有一个整数n（0<n<=10000）;
随后有n行，每行是一个排列；

输出描述:

输出一个整数m，占一行，m表示排列是第几位；

样例输入:

3
abcdefghijkl
hgebkflacdji
gfkedhjblcia

样例输出:

1
302715242
260726926

AC代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<sstream>
#include<iostream>
using namespace std;

int fact[13];
string a,s;
void f()///打印阶乘表
{
    fact[0]=fact[1]=1;
    for(int i=2;i<13;i++)
        fact[i]=fact[i-1]*i;
}

int num(char b)
{
    string str="";
    int len=s.size();
    for(int i=0;i<len;i++)///把字符b截掉，更新后的字符串放在str里，等下再还给s，相当于更新s
    {
        if(s[i]!=b)
            str=str+s[i];
    }
    for(int i=0;i<len;i++)
        if( b==s[i] )
        {
            s=str;      ///返回i之前再复制
            return i;
        }
    return 0;
}

int cantor()
{
    int res=0;
    int lena=a.size();
    for(int i=0;i<lena;i++)
    {
        res=res+ num(a[i])*fact[11-i];
    }
    return res;
}

int main()///NYOJ139，康托展开
{
    f();
    int t;
    cin>>t;
    while(t--)
    {
        cin>>a;
        s="abcdefghijkl";///全局变量s作为副本，每次减少一个字符，表示该字符已经出现过了
        printf("%d
",cantor()+1);
    }
    return 0;
}

143-第几是谁？

内存限制:64MB 时间限制:3000ms
难度:3