首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >康托逆运算

康托逆运算

作者头像
Max超
发布2019-01-21 14:51:14
3030
发布2019-01-21 14:51:14
举报

例1 {1,2,3,4,5}的全排列,并且已经从小到大排序完毕 (1)找出第96个数 首先用96-1得到95 用95去除4! 得到3余23 有3个数比它小的数是4 所以第一位是4 用23去除3! 得到3余5 有3个数比它小的数是4但4已经在之前出现过了所以第二位是5(4在之前出现过,所以实际比5小的数是3个) 用5去除2!得到2余1 有2个数比它小的数是3,第三位是3 用1去除1!得到1余0 有1个数比它小的数是2,第二位是2 最后一个数只能是1 所以这个数是45321 (2)找出第16个数 首先用16-1得到15 用15去除4!得到0余15 用15去除3!得到2余3 用3去除2!得到1余1 用1去除1!得到1余0 有0个数比它小的数是1 有2个数比它小的数是3 但由于1已经在之前出现过了所以是4(因为1在之前出现过了所以实际比4小的数是2) 有1个数比它小的数是2 但由于1已经在之前出现过了所以是3(因为1在之前出现过了所以实际比3小的数是1) 有1个数比它小得数是2 但由于1,3,4已经在之前出现过了所以是5(因为1,3,4在之前出现过了所以实际比5小的数是1) 最后一个数只能是2 所以这个数是14352


题目 求出字符“abcdefghjklmnopq”的第9898999个全排列顺序

#include<iostream>
#include<vector>
#define N 17
using namespace std;
int cal(int n)
{
    int x = 1;
    for(int i = 1; i <= n; i++)
    {
        x *= i;
    }
    return x;
}
int main()
{
    int n = 9898999;
    vector<char> c,ve;
    int u,v;
    u = n;
    //用于抽取数字
    for(int i = 0; i < N; i++)
    {
        c.push_back(i+'a');
    }
    for(int i = N-1; i > 0; i--)
    {
        v = u%cal(i);
        u = u/cal(i);
        ve.push_back(c[u]);
        c.erase(c.begin()+u);
        u = v;
    }
    //将最后一个数提取出来
    ve.push_back(c[0]);
    for(int i = 0;  i < N; i++)
    {
        cout << ve[i] ;
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年03月25日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档