首页 > 代码库 > 输出n的全排列的字典序编号为k的全排列
输出n的全排列的字典序编号为k的全排列
n个元素{1,2,•••，n}有n!个不同的排列。将这n!个排列按字典序排列。并编号为0,1,2.....，n!-1。每 个排列的编号为其字典序的值。例如。当n=3时，其字典排序为：123,132,213,232,312,321，这六个数的字典序值分别为 0,1,2,3,4,5，现给定任意n,输出字典序为k的排列（0<=k<=n！-1）。
这题 也是来源于今年的美团面试题..
一开始 我也无从下手..
后来 看了http://www.cnblogs.com/submarine/archive/2010/04/12/1941268.html
这边 关于 编号的定义 就差不多明白了
2 6 4 5 8 1 7 3
看例子：
tot=0；
比2小的数有1个，则 tot+=1*7！；
比6小的数有4个，则 tot+=4*6！；
比4小的数有2个，则 tot+=2*5！；
比5小的数有2个，则 tot+=2*4！；
比8小的数有3个，则 tot+=3*3！；
比1小的数有0个，则 tot+=0*2！；
比7小的数有1个，则 tot+=1*1！；
比3小的数没有；
（注：在排列中，求比某个数小的数的个数时，排除之前出现过的数）
这是来源于他的博客 介绍 明白了就好
下面是我的代码 自己测试的几组数据都已通过.
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 1010; 6 typedef long long LL; 7 LL fact[size]; 8 bool vis[size]; 9 void init( )10 {11 fact[0] = 1;12 for( int i = 1 ; i<size ; i++ )13 {14 fact[i] = fact[i-1] * i;15 }16 }17 18 int main()19 {20 LL n , k , t , mmin , cnt , temp;21 init( );22 while( cin >> n >> k )23 {24 mmin = 1;25 memset( vis , false , sizeof(vis) );26 for( int i = 1 ; i<=n ; i++ )27 {28 if( k==0 )29 {30 for( int j = mmin ; j<=n ; j++ )31 {32 if( !vis[j] )33 {34 cout << j << " ";35 }36 }37 break;38 }39 else if( k<fact[n-i] )40 {41 while(1)42 {43 if( !vis[mmin] )44 {45 vis[mmin] = true;46 cout << mmin << " ";47 break;48 }49 ++mmin;50 }51 }52 else53 {54 cnt = 0;55 t = k / fact[n-i];56 k -= t * fact[n-i];57 temp = mmin;58 ++ t;59 while(1)60 {61 if( !vis[temp] )62 {63 ++ cnt;64 }65 if( cnt == t )66 {67 vis[temp] = true;68 cout << temp << " ";69 break;70 }71 ++ temp;72 }73 }74 }75 cout << endl;76 }77 return 0;78 }
先折叠起来 大家可以写完后 和我 对拍下
today:
从吹牛b到懂得沉默 就开始慢慢成熟了
输出n的全排列的字典序编号为k的全排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。