康托展开和逆展开

骑猪看日落 2022-06-18 06:07 141阅读 0赞

解析http://www.2cto.com/kf/201311/260148.html

//展开，给你一个排列，让你求这是第几个排列
    //逆展开，给你一个数n，让你求第n个排列是什么 
    #include<iostream>
    using namespace std; 
    int  fac[] = {1,1,2,6,24,120,720,5040,40320}; //i的阶乘为fac[i]
    int a[5]={1,2,3,4,5};
    void f1()
    {
    	int b[5],i,j,num=0,t;
    	for (i=0; i<5; i++)
    	 cin>>b[i];   //求b是第几个排列 
    	for (i=0 ;i<5; i++)
    	{
    		t = 0;
    		for (j=i+1; j<5; j++)
    		{
    			if(b[i]>b[j])
    			{
    				t++; //t为a[i]在数组中为第几大（从0开始） 
    			}
    		}
    		num += t*fac[5-i-1];
    	}
    	cout<<num+1<<endl; //是num个比b小的排列，而b是第num+1个 
    }
    void f2()
    {
    	int i,j,k,t,v[100]={0},b[5];
    	cin>>k; //找第k个排列
    	k--; 
    	for (i=0; i<5; i++)
    	{
    		t = k / fac[5-i-1];
    		for (j=1; j<=5; j++)
    		{
    			if (v[j]==0)
    			{
    				if (t==0)
    				 break;
    				t--;
    			}
    		}
    		b[i] = j;
    		v[j] = 1;
    		k = k % fac[5-i-1];
    	}
    	for (i=0 ;i<5; i++)
    	 cout<<b[i]<<" ";
    }
    int main()
    {
    	f1();//展开 
    	f2();//逆展开 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关【日常学习】【数学/哈希】康托展开

康托展开是什么呢？（以下内容引自CSDN用户[zhongkeli ][zhongkeli]原文地址：[http://blog.csdn.net/zhongkeli/arti

我就是我/ 2022年08月04日 11:50/ 0 赞/ 170 阅读

相关全排列的编码与解码——康托展开及其逆展开

一、康托展开：全排列到一个自然数的双射 X=an\(n-1)!+an-1\(n-2)!+...+ai\(i-1)!+...+a2\1!+a1\0! ai为整数，

约定不等于承诺〃/ 2022年07月15日 10:40/ 0 赞/ 116 阅读

相关排列序列（康托展开）

X星系的某次考古活动发现了史前智能痕迹。这是一些用来计数的符号，经过分析它的计数规律如下：（为了表示方便，我们把这些奇怪的符号用a~q代替） abcdefgh

﹏ヽ暗。殇╰゛Y/ 2022年06月18日 07:06/ 0 赞/ 121 阅读

相关康托展开和逆展开

解析http://www.2cto.com/kf/201311/260148.html //展开，给你一个排列，让你求这是第几个排列 //逆展开，给你一个数n

骑猪看日落/ 2022年06月18日 06:07/ 0 赞/ 142 阅读

相关康拓逆展开

康托展开的逆运算： \{1,2,3,4,5\}的全排列已经从小到大排序，要找出第16个数： 1. 首先用16-1得到15 2. 用15去除4! 得

以你之姓@/ 2022年06月17日 08:41/ 0 赞/ 136 阅读

相关详解--康托展开

康托展开： X=an\(n-1)!+an-1\(n-2)!+…+ai\(i-1)!+…+a2\1!+a1\0! ai为整数，并且0<=ai<i(1<=i<=n) 应

àì夳堔傛蜴生んèń/ 2022年06月10日 12:27/ 0 赞/ 150 阅读

相关蓝桥排列序数（康托展开）

标题：排列序数 X星系的某次考古活动发现了史前智能痕迹。这是一些用来计数的符号，经过分析它的计数规律如下：（为了表示方便，我们把这些奇怪的符号

曾经终败给现在/ 2022年05月27日 22:37/ 0 赞/ 151 阅读

相关康托展开

康托展开是一个全排列到一个[自然数][Link 1]的[双射][Link 2]，常用于构建[哈希表][Link 3]时的空间压缩。康托展开的实质是计算当前排列在所

古城微笑少年丶/ 2022年05月17日 22:49/ 0 赞/ 169 阅读

相关【算法】康托展开和逆康托展开

文章目录康拓展开逆康拓展开康拓展开 > 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时

你的名字/ 2022年04月01日 06:20/ 0 赞/ 172 阅读

相关 [洛谷P5367]【模板】康托展开

题目大意：给定一个$n$的排列，求它在$n$的全排列中的名次题解：康托展开，对于一个全排列，第$i$为有$n+1-i$种选择，用变进制数表示，这一位就是$n+1-i$进制。

分手后的思念是犯贱/ 2021年12月09日 21:11/ 0 赞/ 228 阅读