数字,文字康托展开数与康托逆展开序列排序在线计算器_三贝计算网_23bei.com
元素总数
排列总数
对应康托展开数
 
 


 

好东西得来不易,【一键收藏】本计算器!请先【登录】或【注册】。

CTRL+A :选中全部,CTRL+C:复制,CTRL+V:粘贴。【注册】【APP客户端】【使用必读

分类:文字处理 标签:康托展开 康托逆展开 康托公式 排序  工具ID:214

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

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

}

 

微信扫一扫
收藏计算器
分享朋友圈

三贝计算网-23bei.com

  • 数组元素个数统计,反序,按大小排序处理工具
  • 中文汉字简体转繁体|繁体转简体在线转换工具软件
  • Escape在线加密/解密工具软件
  • 摩尔斯码在线加密,解密工具|中文摩尔斯密码在线计算软件
  • 在线加密/解密工具|AES、DES、3DES、Rabbit、RC4、RC4Drop加密/解密软件
  • CryptoJS实现3DES加密,解密在线调试软件|数据加密标准(3DES)在线计算器
  • CryptoJS实现DES加密,解密在线调试软件|数据加密标准(DES)在线计算器
  • PHP加密库OpenSSL实现AES加密,解密调试软件(附源码)在线计算器
  • CryptoJS实现AES加密,解密在线调试软件|高级加密标准(AES)在线计算器
  • 散列哈希值(PBKDF2)在线计算器
  • 散列哈希值(MD5、SHA1、HmacSHA1、RIPEMD-160等)在线计算器
  • 集合,数组滤除(去)重复元素在线处理工具
  • 在线随机数生成器|随机数字生成软件
  • JS编程将复制的(表格文本)转换为(数组元素)变量的工具
  • JS代码中的中文,汉字(GBK,UTF-8)转Unicode编码工具
  • 数字,文字康托展开数与康托逆展开序列排序在线计算器
  • ASCII码,中文汉字与Uincode编码相互转换在线计算器
  • 英文字母(大写小写转换)在线处理工具
  • 人民币小写(数字)金额转大写(汉字)在线计算器
  • 文本文字(去除换行符,格式,空格)在线净化排版工具
  • 文本文字(去除换行符,回车,空格),文字替换在线处理工具
  • 在线随机密码(钥)生成器|随机密码生成软件
  • 文本文字(自动换行,分行)在线处理工具
  • ASCII/GBK/GB2312中文汉字区位码,内码,编码在线查询软件
  • 文本文字(字数,字符数,字节数)统计在线计算器
  • 三贝二维码在线生成器
  • Base64编码/解码在线计算工具
  • UrlEncode编码/UrlDecode解码在线计算工具
  • MD5加密(16位,32位,大写,小写)在线计算器