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


 

CTRL+A ：选中全部，CTRL+C：复制，CTRL+V：粘贴。 【使用必读】

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

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

输入用空格或(字母半角)逗号隔开的整数或字母序列，如：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;

}

 

对此计算器不满意或未找到合适的计算器？本网站免费订制专用计算器…… 报错/建议 讨论专区

相关推荐