康托展开（Cantor expansion）

Posted on   |   In   |  

算法描述

把一个整数 X 展开成如下形式：

X = a[n] * (n-1)! + a[n-1] * (n-2)! + ... + a[i] * (i-1)! + ... + a[1] * 0!

其中，a[i] 为整数，并且 0 <= a[i] < i (1 <= i <= n)

适用领域范围：解决一些序列问题的算法．

实例一

{1,2,3,4,…,n} 表示 1,2,3,…,n 的排列．如 {1,2,3} 按从小到大排列一共6个：123, 132, 213, 231, 312, 321．代表它们的数字是：1, 2, 3, 4, 5, 6，也就是把10进制的某个数与一个排列对应起来．

他们间的对应关系可由康托展开来找到．

如我想知道 321 是 {1,2,3} 中第几个小的数时，可以这样考虑：

第一位是3：小于3的数有1、2．所以有2*2!个；

第二位是2：小于2的数只有一个就是1，所以有1*1!=1；

第三位是1：小于1的数有0个，也就是0*0!=0；

所以小于321的{1,2,3}排列数有2*2!+1*1!=5个；

所以321是第6个小的数。 

2*2!+1*1!+0*0!就是康托展开。

再举个例子：1324是{1,2,3,4}排列数中第几个大的数：

第一位是1，小于1的数没有，是0个，0*3! 

第二位是3，小于3的数有1和2，但1已经在第一位了，所以只有一个数2，1*2! 。

第三位是2，小于2的数是1，但1在第一位，所以有0个数，0*1! ，

所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个小数。

C 语言代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//参数 int s[] 为待展开之数的各位数字，如需展开2134，则s[4] = {2,1,3,4}
//参数 n 为待展开的数字个数，这里是4
//阶乘表 long int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}

long cantor(int s[], int n)
{
    long int i, j, temp, num;

    num = 0;
    for(i=0; i<n; i++)
    {
        temp = 0;
        for(int j=i+1; j<n; j++)
        {
            if(s[j]<s[i])
                temp++; //判断几个数小于它
        }
        num += fac[n-i-1] * temp;   //(或num = num + fac[n-i-1] * temp;)
    }
    return num+1;
}

实例二

在魔方风靡全球之后不久，Rubik先生发明了它的简化版――魔板。魔板由 8 个同样大小的方块组成，每个方块颜色均不相同，可用数字 1-8 分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方 向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。

例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为： 

1 2 3 4 
8 7 6 5

对于魔板，可施加三种不同的操作，具体操作方法如下： 

A: 上下两行互换，如上图可变换为状态87654321

B: 每行同时循环右移一格，如上图可变换为41236785 

C: 中间4个方块顺时针旋转一格，如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种．

解题思路：

1: 把初始状态转换成 12345678 这个状态

2: 把目标状态按照初始状态的转换进行转换

    例如：初始状态为 63728145，目标状态为 86372541

    将初始状态转换为 12345678，目标状态相应转化为 51234876

    注释：初始状态6在1的位置上，将初始状态和目标状态中的6都用1代替，一次类推．

3: 使用康托展开和广度优先算法生成从12345678这个状态到其他所有状态的路径，即：8!种

   注释：使用广度优先可以确保从12345678这个状态转换到的任何其他状态所经过的变换是最少的，这样就可以

   保证最后结果是我们需要的字典序最小的那种．

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

using namespace std; 

const int MAXN = 40321; //由于此题数字1~8，康托展开的所有情况为8!，共40320种 
const int fac[8] = {1,1,2,6,24,120,720,5040}; //康托展开中用到的0~7的阶乘 
string ans[MAXN]; //存储各状态的变化步骤，预处理完成 

struct node
{
    int a[8];
    int n;
}u,v;

void A(node &t) //A操作 
{
    swap(t.a[0],t.a[7]); 
    swap(t.a[1],t.a[6]); 
    swap(t.a[2],t.a[5]); 
    swap(t.a[3],t.a[4]);
}

void B(node &t) //B操作 
{
    swap(t.a[3],t.a[2]); 
    swap(t.a[2],t.a[1]); 
    swap(t.a[1],t.a[0]); 
    swap(t.a[4],t.a[5]); 
    swap(t.a[5],t.a[6]); 
    swap(t.a[6],t.a[7]);
}

void C(node &t) //C操作 
{
    swap(t.a[1],t.a[6]); 
    swap(t.a[6],t.a[5]); 
    swap(t.a[5],t.a[2]);
}

int contor(node &t) //康托展开
{
    int tmp, num = 0;
    for(int i=0; i<8; i++)
    {
        tmp = 0;
        for(int j=i+1; j<8; j++)
        {
            if(t.a[j] < t.a[i])
                tmp++;
        }
        num += tmp*fac[7-i];
    }
    return num;
} 

void Init(void)
{
    void (*ptr[3])(node&); //定义函数指针 
    ptr[0] = A; ptr[1] = B; ptr[2] = C; //指向对应函数方便处理 

    int mark[MAXN] = {0}; //设置标记 

    mark[0] = 1;

    for(int i=0; i<8; i++) //由初始状态12345678开始 
        u.a[i] = i+1;
      
    u.n = contor(u);

    queue<node>que;
    que.push(u);
    while(!que.empty())
    {
        u = que.front();
        que.pop(); 
        for(int i=0; i<3; i++) //三种变换 
        {
            v = u;
            (*ptr[i])(v);
            v.n = contor(v); //对副本执行操作并康托展开 
            if(mark[v.n] == 0) //重复 
            {
                char ch = 'A' + i;
                ans[v.n] = ans[u.n] + ch; //记录步骤 

                mark[v.n] = 1; //标记 
                que.push(v);
            } 
        }
    }
}

int main()
{
    Init();
    string str1, str2;
    char a[10] = {0}, b[10] = {0};
        
    while(cin >> str1 >> str2)
    {
        int n[10];
            
        for(int i=0; i<8; ++i)
        {
            a[i] = str1[i] - '0';
            b[i] = str2[i] - '0';
        }

        for(int i=0; i<8; i++) //把初态置换成12345678 
            n[a[i]-'0'] = i+1;

        for(int i=0; i<8; i++) //把目标状态相对于初态置换 
            u.a[i] = n[b[i]-'0'];
              
        cout << ans[contor(u)] << endl; //输出由12345678到目标态的步骤 
    }
    return 0;
}