马老师的烦恼

01  动物园 6·1 节来啦

又到了一年一度的61儿童节，动物园里充满了欢声笑语。不仅有好吃的好喝的，还有各种好玩的活动。当然最重量级的就是小朋友们的节目表演啦。

马老师也开始紧锣密鼓的筹备节目。

马老师平时熟读《孙子兵法》，深知阵型的重要性，先让同学们变换一下阵型。

马老师的博学也派上了用场，迅速下发了指令，满怀期待的看着同学们。

3秒后，同学们依然保持动能守恒，就是原地不动啦。

原来是小朋友们平时没好好学习《孙子兵法》，根本听不懂老师说的啥。

马老师长叹一声，只好放弃。那就做简单的全排列吧，这个你们肯定学过。

但正式表演的时候同学有很多，如果有20个同学，那马老师怎么下发指令呢，总不能说“同学们，变换队列为123456...20”。

马老师陷入了沉思。。。

02  问题建模

能否找到一种简单的方法来指定是哪一种排列呢，比如给每个排列队形取一个名字，如“苹果队形，香蕉队形...”，这样也行，不过要想这么多名字也不容易。

要是能给每个不同的排列按顺序编号就完美了。

这样问题就转化为：能否找一个编号与排列的一一映射，简称双射。

。

这就要说到一个著名的数学定理了，康托展开。

03  康托展开

康托展开是全排列与自然数的双射，常用于空间压缩。
本质是计算当前排列在所有由小到大全排列中的顺序，因此可逆。

3.1  排列  自然数

3.2  自然数  排列

04  代码实现

4.1  康托编码

// 0-9的阶乘  
const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};  
  
int cantor(int a[], int n) {  
    int ans = 0;  
    for (int i = 0; i < n; ++i) {  
        int lessThan = 0;  
        for (int j = i + 1; j < n; ++j) {  
            if (a[j] < a[i]) lessThan++;  
        }  
        ans += lessThan * FAC[n - i - 1];  
    }  
    return ans;  
}

4.2  康托解码

void decode(int ans[], int x, int n) {  
    bool visit[9] = {false};  
    for (int i = 0; i < n; ++i) {  
        ans[i] = x / FAC[n - i - 1];  
        int j, order = 0;  
        for (j = 0; j < n; ++j) {  
            if (!visit[j]) {  
                if (ans[i] == order) break;  
                order++;  
            }  
        }  
        ans[i] = j + 1;  
        visit[j] = true;  
        x %= FAC[n - i - 1];  
    }  
}

例题poj1077

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

推荐关注「算法爱好者」，修炼编程内功

点赞和在看就是最大的支持❤️