Cantor Expansion

algorithm

realization

 2021/01/08  Share

9位康托展开代码：

#include<bits/stdc++.h>
using namespace std;
int factorial[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int a[10];
int CantorExpansion(int *stat) {
	int index = 0, counted;
	for(int i = 0; i < 9; ++i) {
		counted=0;
		for(int j = i + 1; j < 9; ++j)
			if(stat[j] < stat[i])
				++counted;
		index += counted * factorial[8 - i];
	}
	return index;
}
int main(int argc, char *argv[]) {
	for(int i = 0; i < 9; ++i) cin >> a[i];
	cout << CantorExpansion(a) << endl;
	return 0;
}

康托展开从一个不重复序列中得到某个排列在全排列中的字典序。

以9位(01235678)为例：

State	012345678	012345687	012345768	…	876543210
Cantor Value	0	1	2	…	362880

原理:

从第一位开始，寻找往后序列中比第一位小的数，将其放在首位，剩下的数全排列
固定第一位，寻找往后序列比第二位小的数，将其放在第二位，剩下的数全排列
往后按此规律即可，直到遍历到最后一位
则返回值:
$X = a_n\cdot(n-1)!+a_{n-1}\cdot(n-2)!+a_{n-2}\cdot(n-3)!+...+a_i\cdot(i-1)!+...+a_1\cdot0!,\\ 其中0\le{a_i}\le{9}(1<=i<=n)$

Author: Endsieg77

Link: https://endsieg77.github.io/2021/01/08/Cantor-Expansion/

Post on: January 8th 2021, 10:21:57 pm

Update on: January 8th 2021, 10:23:28 pm

Next Post

Centos Cpp17 Config
Previous Post

WATERLOO 2021-1-8

CATALOG

1. 9位康托展开代码：
1. 1.1. 康托展开从一个不重复序列中得到某个排列在全排列中的字典序。
2. 1.2. 原理:



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true