今天保研的小朋友来所里笔试+面试。。。。全国各大名牌高校都往这里挤啊。。。
有序立方体
问题描述：
给定一个由N个互不相同的整数构成的序列{x0, x1, ..., xN-1 }，如果其元素是按照升序排列的：x0 < x1 < ... < xN-1，那么我们称之为有序数列
类似地，如果一个N x N的二维数组满足它的所有行和所有列都是有序数列的话，那么它就是一个有序平面。
于是我们可以定义一个N x N x N的三维数组为有序立方体，如果它垂直于三个轴向的所有截面都是有序平面。如下图所示，z = 0定义了立方体垂直于z轴的顶截面，而z = N – 1则定义了立方体垂直于z轴的底截面。在本题中，1到N3的所有整数均出现且仅出现一次。
要求编写函数sortCube，使其以尽量少的交换次数将初始立方体变换为有序立方体。
输入参数：
• int N表示立方体每个维度的尺寸大小；
• int initCube[N*N*N]为初始立方体配置，按照平面优先和行优先的顺序将三维数组表示为一维向量，即立方体中坐标(X, Y, Z)的数据在initCube中的索引值为N*N*Z + N*Y + X；。
输出参数：
• 按照"X1,Y1,Z1-X2,Y2,Z2"的格式输出所需交换操作步骤。这里'X1', 'Y1', 'Z1', 'X2', 'Y2', 'Z2'表示0到N-1之间的数据下标，而每一个元素则表示互换(X1, Y1, Z1)与(X2, Y2, Z2)位置的数据。
这里给出我的想法吧：
首先给出一个定义，在原点处我们假设其坐标为（0,0,0）。对于3*3*3立方体，从一个很显然的角度来说，把立方体沿着对角线立起来。。我们可以注意到这个立方体可以被分为很多层，第一层是（0,0,0）第二层是（0,0,1）（1,0,0）（0,1,0）,第三层是（0,0,2）（2,0,0）（0,2,0）（1,0,1）（1,1,0）（0,1,1），这样子可以扩展地想一下，总共可以分为7层，这七层中可以用曼哈顿距离分类：
距离： 0 1 2 3 4 5 6
点数： 1 3 6 7 6 3 1
总共有27个点了。。。
如果扩展到n*n*n的话，我们依然使用 曼哈顿距离来分类。假设n无限大的话，
在第n层中会有几个点呢？这个可以等价到这样一个问题，x+y+z=n
x>=0 y>=0 z>=0 的正整数解的个数。这个问题高中生都会。。。。
等价于从n+2个物品中选择2个。。。C（2，n+2）
然后对于一个给定的n，我们究竟有多少层呢？。。。简单的观察就知道，前后对称。。
以此正方体体对角线开始减1 3 。。。直至构造到（0,0，N-1）,此时停止构造。。这个时候，上面推导的那个公式C(2,n+2)就不对了。。此时剩余了多少层呢？。。。同样的哈密顿距离告诉我们N层。。。那么这n层怎么搞呢？
x+y+z=M
N>x>=0 N>y>=0 N>z>=0 就是这样一个方程。。。M的范围在[0,3*N-1]。。。有想法了吧？！
下面将是这个问题的核心部分，也是最精彩的部分。。。给出了3*N层，把它抽象成一个3*N个点的图。。遍历给定的一个特殊的立方体，判断相应位置中的数是属于那一层的。如果属于该层，当然不用什么交换了之类的操作，如果不属于，把当前层的点与它隶属层的点连接一条有向边，指向它的目标层。遍历操作结束，就构造成了一张图！
有点眉目了么？没错，就是置换群的变种！此时，我们只要在图中寻找回路，然后求得回路的边数，一个回路组成一个置换群。答案就是所有回路边数-回路数。。。。
的确是很bug的一道题目。。去年的这个时候看过这个题目。。没有想出解答方案。。当然面试的时候比较简单。。直接是求出一个方案，没必要要求最小。。。今天终于想到了一个解决方案。。。问题的思考是慢慢的一步一步的。。。