通俗易懂的康托展开（C++实现）

简介： （一）背景介绍

在备战蓝桥杯的过程中，遇到了康托展开式，博主当时也是弄的焦头烂额，最后通过不断的模拟，搜集资料，写出了一个还比较好懂（我这么认为）的写法。

（二）环境介绍

（1）机器：Lenovo小新pro16 Windows10

（2）开发工具：Visual studio 2020

（3）开发语言：C++

话不多说，直接上代码，解析都在代码注释：

/*
* 康托展开式是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩
* 康托展开实质：计算当前排列在所有由小到大的全排列中的名次，因此可逆
* 输入正整数 N ，输入从 1 到 N 的某个排列，求该排列在全排列中的排名位置
* 如输入 N 为 3 ，全排列为 123 132 213 231 312 321 
* 输入排列 2 1 3 ， 2 1 3 在全排列中排第三 ，而康托展开值是该排列前有多少个排列
*/
/*举例：输入 5763214，计算其序号
* ①ans = 0 , tmp = 0 , 字符串长度为 7
* ②第一个数 5 ，进入循环，遍历 7 6 3 2 1 4 ，其中有 3 2 1 共三个数比 5 小，所以 tmp = 3
* ③ans = ans + tmp * factorial[6] = 0 + 3 * 6!
* ④第二次循环，开始看第二个数 7 ，tmp = 0
* ⑤遍历 6 3 2 1 4 ，其中有 6 3 2 1 4 共五个数比 7 小，所以 tmp = 5
* ⑥ans = ans + tmp * factorial[5] = 3 * 6! + 5 * 5!
* ⑦依次类推………………
*/
#include
#include
using namespace std;
int factorial[20];//存放阶乘, 0!  1!  2!  3!  …………
void get_fac(string str)//获得阶乘
{
	int n = str.size();//也可以用 .length， n 为输入的排列位数，如 51342 是五位，则这里获得五个阶乘
	factorial[0] = factorial[1] = 1;// 0！和 1！都是 1 
	for (int i = 2; i < n; ++i)
	{
		factorial[i] = factorial[i - 1] * i;
	}
	return;
}
int cantor(string str)//康托展开
{
	int ans = 1;//序号，12345……康托展开是 0 ，计算时结果为 0 ，ans 无法记录（增加），但其算一个序号，所以 ans 从 1 开始
	int len = str.size();//字符串长度
	for (int i = 0; i < len; ++i)
	{
		int tmp = 0;//在下面的循环记录第 i 位的后面比其小的数的个数
		for (int j = i + 1; j < len; ++j)//从第 i 位的后面一位开始遍历后面的数
		{
			if (str[i] > str[j])  ++tmp;//如果后面的某位数小于第 i 位数，则符合康托展开要求
		}
		ans += tmp * factorial[len - 1 - i];//因为阶乘数组中是 0！ 1！ 2！ 3！ …… 所以依次从后面往前乘，然后开始外循环的第二次循环，tmp 重新赋值为 0
		/*符合康托展开公式 
		X = An * (n - 1)! + An-1 * (n - 2)! + …… + A2 * 1! + A1 * 0!
		An 是第 i 位后面的数中比其小的数的个数
		*/
	}
	return ans;
}
int main()
{
	string str;
	cin >> str;//输入排列
	get_fac(str);
	cout << cantor(str) << endl;
	return 0;
}

博主新人，如果代码有什么不对的地方，还请斧正！