数字,文字康托展开数与康托逆展开序列排序在线计算器
元素总数
排列总数
对应康托展开数
 
 


 

CTRL+A ：选中全部，CTRL+C：复制，CTRL+V：粘贴。 【使用必读】【本站支持微信扫码登录了】【除了计算器还有这些功能可用】

分类： 文字处理 标签：康托展开康托逆展开康托公式排序 工具ID：214 阅读：1986 收藏

本计算器用于康托公式中康托展开与康托逆展开序列，按指定康托数排序。

输入用空格或(字母半角)逗号隔开的整数或字母序列，如：1 2 3 4 5 ……等，点击计算可求出输入元素总数和排列总数以及输入序列的康托展开数。如果同时输入康托逆展开数计算器将输出指定康托展开数(康托逆展开数)所对应的序列。

注意：

1）如果输入元素存在相同元素，则各元素组成的序列并非单纯排列，而有组合存在，计算值会有误差或重复。

2）本计算器中康托展开数和指定康托逆展开数从0开始，取值范围为（0到N-1），其中N为输入元素的排列总数，即最小的序列对应康托展开数为0，如需从1开始，请自行在计算结果或指定康托逆展开数中加1。

例如：

输入 1 2 3 4 5等5个元素，该序列是其所有排列中数值最小的序列，故而，其对应的康托展开数为0。该序列的所有排列中，数值第二小的序列是1 2 3 5 4，当指定康托逆展开数为1时（即：求其第2小序列的康托逆展开），点击“计算”按扭，计算器将输出对应序列1 2 3 5 4。

康托展开式：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<=a[i]

康托展开表示的是当前排列在n个不同元素的全排列中的名次（由小到大，从0开始），康托逆展开就是根据某个排列的在总的排列中的名次来确定这个排列。注意，这个模板中康托逆展开求出的排列是一个连续序列的排列。

C++实现代码如下：

#include

using namespace std;

typedef long long ll;

const int N = 100 + 10;

char s[N];

ll fact[N];

void fact_table() //阶乘表，示例仅打表到20，

{

    fact[0] = 1;

    for(int i = 1; i <= 20; i++) fact[i] = i * fact[i-1];

}

ll Cantor_expansion(char *s)

{

    ll res = 0;

    int len = strlen(s);

    for(int i = 0; s[i]; i++)

    {

        int rnk = 0;

        for(int j = i+1; s[j]; j++)

            if(s[i] > s[j]) rnk++;

        res += rnk * fact[len-i-1];

    }

    return res; //返回康托展开数，即输入序列是所有排列中的第几大序列

}

void Cantor_inverse_expansion(ll n, int m)

{

    //n是在全排列中的名次，注意是从0开始计数的，若从1开始计数则要减去1。m是元素个数

    vector num;

    int arr[N], k = 0;

    for(int i = 1; i <= m; i++) num.push_back(i);   //填充num向量数组

    for(int i = m; i >= 1; i--)

    {

        ll r = n % fact[i-1];

        ll t = n / fact[i-1];

        n = r;

        sort(num.begin(), num.end());          //num向量数组排序

        arr[k++] = num[t];

        num.erase(num.begin() + t);            //删除num向量数组第t个元素

    }

    for(int i = 0; i < k; i++) printf("%d", arr[i]);

    printf(" ");

}

int main()

{

    fact_table();

    while(~scanf("%s", s))

    {

        int len = strlen(s);

        ll res = Cantor_expansion(s);      //求出此排列的名次

        printf("%lld ", res);

        Cantor_inverse_expansion(res, len);  //根据排列的名次复原此排列

    }

    return 0;

}

 

最新搜索： RS des 40L/h 50b5cda4 91330302MA CRC码 GB2312 编码规 IBM 风管三通 N.WG fc14a8 tO2 过电流计算 三角面积 常用对数 超级电容器 12111222 3 CFM 字 风管面积 x²+x-220=0 (结果) 翅片管 管径流量 判别式 物理单摆周期 入射角 是 三次 典型 棱台 液体压力流速 压力流速 放电时间 换热管管 260 11 Cam 需要量 多项式异或 圆锥 总传热系数计算公式 0.0000625 经 GHz 正三通面积 计数器 校验异或、 路易斯 HCO3－ 天 1.00073883 85OF 三通面积 统计 直线运动 √7.68/6280 合数 加工工时 年金终值系数 圆三通 0.642 Q235 4B+8 请35 铁 做功指数 rd 7.68/6280 圆柱体 棱锥 正切1 根号九 界限 血肌酐及时 A 焓差 三维向量 厘米换像素 文本转 发生 高张溶液 锌 三通风管 特征值 十进制转三十二 16进制浮 固相悬浮临界搅拌转速 品 MBCR 音箱分频器 年金终值计算公式 0.11111 1744 4个 asc N 结构力学 三角形体积 搅拌机功率
对此计算器不满意或未找到合适的计算器？本网站免费订制专用计算器…… 报错/建议 讨论专区

相关推荐