康托展开可以建立1~n全排列到n!的一一映射，常用于字符串哈希，这也是优化时间空间的一种方法。

        康托展开只能用于全排列的映射。对于1~n的一个排列，康托展开可以得到这个排列在全排列中按字典序的序号(12…n序号为0)，这样便可以建立字符串到[0,n!)的一个映射。
        假设序列为$s_1s_2…s_n$，具体做法如下：

  1. 从左到右依次求出$s_i$的逆序数$a_i$，需要两遍循环。
  2. 康托展开的值为$\displaystyle\sum_{i=1}^na_i(n-i)!$。

        需要预处理出0~n-1的阶乘，注意0!=1。
        康托展开的原理是易于理解的，他通过找逆序数并乘以排列数的方式来求小于已知序列的排列有多少种，这样便得到已知序列在全排列中的序号。
        那么根据康托展开的值如何得到原排列呢？这就是逆康托展开。设值为x，逆展开算法如下：

  1. 开一个数组记录哪些数已经被选了，初始化全未被选。
  2. 对于序列的第i位（从1开始），计算$x/(n-i)!$（带余除法）的值p。
  3. 从未被选的数中找到第p+1小的数m，序列的第i位便为m。标记m已被选，更新$x=x mod (n-i)!$。
  4. 重复2和3步，直到序列的所有数均被求出。

        逆展开原理也是易于理解的。易知每一次求出的p就是逆序数，通过逆序数可以方便地推知第i位的值。
        下面通过经典八数码问题（洛谷P1379）来应用康托展开。

题目描述

        在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

        输入初始状态，一行九个数字，空格用0表示

输出格式：

        只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

        八数码问题是经典的搜索类问题，难度在于状态的描述（这是一个排列），康托展开可以很好地解决这个问题。
        用康托展开将每一个排列化为数字，用于判重和搜索，必要时再逆展开为排列，可以降低时间空间复杂度。另外需要注意的是本题需要用BFS（因为要求最少步数）。

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
#include<iostream>
#include<queue>

using namespace std;
int jc[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};//预处理阶乘
bool vis[362880] = {false};

inline int Hash(const char *op) {//康托展开
    int ans = 0;
    for (int i = 0, p = 8; i < 9; i++, p--) {
        int s = 0;
        for (int j = i + 1; j < 9; j++)if (op[j] < op[i])s++;
        ans += s * jc[p];
    }
    return ans;
}

inline void cal(int h, char *op) {//逆展开
    bool vis[10] = {false};
    for (int i = 0, p = 8; i < 9; i++, p--) {
        int s = h / jc[p];
        for (int z = 0; z < 9; z++)
            if (!vis[z]) {
                if (s == 0) {
                    op[i] = static_cast<char>(z + '0'), vis[z] = true;
                    break;
                } else s--;
            }
        h %= jc[p];
    }
}

struct Node {
    int h, step, begin;

    Node(int a, int b, int c) : h(a), step(b), begin(c) {}
};

char b[9];
queue<Node> que;

int main() {
    cin >> b;
    for (int i = 0; i < 9; i++) {
        if (b[i] == '0') {
            que.push(Node(Hash(b), 0, i)), vis[Hash(b)] = true;
            break;
        }
    }
    Node p(0, 0, 0);
    int h;
    while (!que.empty()) {
        p = que.front(), que.pop(), cal(p.h, b);
        if (p.h == 46685) {//46685是目标状态的康托展开值
            cout << p.step;
            return 0;
        }//下面分四个状态转移
        if (p.begin % 3 != 0) {
            swap(b[p.begin], b[p.begin - 1]), h = Hash(b), swap(b[p.begin], b[p.begin - 1]);
            if (!vis[h])que.push(Node(h, p.step + 1, p.begin - 1)), vis[h] = true;
        }
        if ((p.begin + 1) % 3 != 0) {
            swap(b[p.begin], b[p.begin + 1]), h = Hash(b), swap(b[p.begin], b[p.begin + 1]);
            if (!vis[h])que.push(Node(h, p.step + 1, p.begin + 1)), vis[h] = true;
        }
        if (p.begin > 2) {
            swap(b[p.begin], b[p.begin - 3]), h = Hash(b), swap(b[p.begin], b[p.begin - 3]);
            if (!vis[h])que.push(Node(h, p.step + 1, p.begin - 3)), vis[h] = true;
        }
        if (p.begin < 6) {
            swap(b[p.begin], b[p.begin + 3]), h = Hash(b), swap(b[p.begin], b[p.begin + 3]);
            if (!vis[h])que.push(Node(h, p.step + 1, p.begin + 3)), vis[h] = true;
        }
    }
}

        为了更好地降低时间复杂度，本题最好用双向BFS。双向BFS只适用于目标状态已知的情况（比如本题）。做法是开两个队列，分别从初始状态和目标状态转移，直到两个队列中出现重合状态。在某些情况下，这种方法可以大大提升效率。需要注意双向BFS时,visited数组需要额外记录这个状态是哪一个分枝访问到的。在转移时如果发现下一个状态已经被另一个分枝访问到了，则可以得出答案。
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
#include<iostream>
#include<queue>
#include<cstdlib>

using namespace std;
int jc[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int vis[362880] = {0}, step1[362880] = {0}, step2[362800] = {0};

inline int Hash(const char *op) {
    int ans = 0;
    for (int i = 0, p = 8; i < 9; i++, p--) {
        int s = 0;
        for (int j = i + 1; j < 9; j++)if (op[j] < op[i])s++;
        ans += s * jc[p];
    }
    return ans;
}

inline void cal(int h, char *op) {
    bool vis[10] = {false};
    for (int i = 0, p = 8; i < 9; i++, p--) {
        int s = h / jc[p];
        for (int z = 0; z < 9; z++)
            if (!vis[z]) {
                if (s == 0) {
                    op[i] = static_cast<char>(z + '0'), vis[z] = true;
                    break;
                } else s--;
            }
        h %= jc[p];
    }
}

inline void print(int x) {
    cout << step1[x] + step2[x];
    exit(0);
}

struct Node {
    int h, begin;

    Node(int a, int c) : h(a), begin(c) {}
};

char b[9];
queue<Node> que, que2;

int main() {
    cin >> b;
    for (int i = 0; i < 9; i++) {
        if (b[i] == '0') {
            que.push(Node(Hash(b), i)), vis[Hash(b)] = 1;
            break;
        }
    }
    if (Hash(b) == 46685) {
        cout << 0;
        return 0;
    }
    que2.push(Node(46685, 4)), vis[46658] = 2;
    Node p(0, 0);
    int h;
    while (!que.empty() || !que2.empty()) {
        if (!que.empty()) {//第一个队列转移
            p = que.front(), que.pop(), cal(p.h, b);
            if (p.begin % 3 != 0) {
                swap(b[p.begin], b[p.begin - 1]), h = Hash(b), swap(b[p.begin], b[p.begin - 1]);
                if (vis[h] == 2)step1[h] = step1[p.h] + 1, print(h);
                if (!vis[h])que.push(Node(h, p.begin - 1)), vis[h] = 1, step1[h] = step1[p.h] + 1;
            }
            if ((p.begin + 1) % 3 != 0) {
                swap(b[p.begin], b[p.begin + 1]), h = Hash(b), swap(b[p.begin], b[p.begin + 1]);
                if (vis[h] == 2)step1[h] = step1[p.h] + 1, print(h);
                if (!vis[h])que.push(Node(h, p.begin + 1)), vis[h] = 1, step1[h] = step1[p.h] + 1;
            }
            if (p.begin > 2) {
                swap(b[p.begin], b[p.begin - 3]), h = Hash(b), swap(b[p.begin], b[p.begin - 3]);
                if (vis[h] == 2)step1[h] = step1[p.h] + 1, print(h);
                if (!vis[h])que.push(Node(h, p.begin - 3)), vis[h] = 1, step1[h] = step1[p.h] + 1;
            }
            if (p.begin < 6) {
                swap(b[p.begin], b[p.begin + 3]), h = Hash(b), swap(b[p.begin], b[p.begin + 3]);
                if (vis[h] == 2)step1[h] = step1[p.h] + 1, print(h);
                if (!vis[h])que.push(Node(h, p.begin + 3)), vis[h] = 1, step1[h] = step1[p.h] + 1;
            }
        }
        if (!que2.empty()) {//第二个队列转移
            p = que2.front(), que2.pop(), cal(p.h, b);
            if (p.begin % 3 != 0) {
                swap(b[p.begin], b[p.begin - 1]), h = Hash(b), swap(b[p.begin], b[p.begin - 1]);
                if (vis[h] == 1)step2[h] = step2[p.h] + 1, print(h);
                if (!vis[h])que2.push(Node(h, p.begin - 1)), vis[h] = 2, step2[h] = step2[p.h] + 1;
            }
            if ((p.begin + 1) % 3 != 0) {
                swap(b[p.begin], b[p.begin + 1]), h = Hash(b), swap(b[p.begin], b[p.begin + 1]);
                if (vis[h] == 1)step2[h] = step2[p.h] + 1, print(h);
                if (!vis[h])que2.push(Node(h, p.begin + 1)), vis[h] = 2, step2[h] = step2[p.h] + 1;
            }
            if (p.begin > 2) {
                swap(b[p.begin], b[p.begin - 3]), h = Hash(b), swap(b[p.begin], b[p.begin - 3]);
                if (vis[h] == 1)step2[h] = step2[p.h] + 1, print(h);
                if (!vis[h])que2.push(Node(h, p.begin - 3)), vis[h] = 2, step2[h] = step2[p.h] + 1;
            }
            if (p.begin < 6) {
                swap(b[p.begin], b[p.begin + 3]), h = Hash(b), swap(b[p.begin], b[p.begin + 3]);
                if (vis[h] == 1)step2[h] = step2[p.h] + 1, print(h);
                if (!vis[h])que2.push(Node(h, p.begin + 3)), vis[h] = 2, step2[h] = step2[p.h] + 1;
            }
        }
    }
}