编码与解码;字符串字典序问题;根据字符串找位序,根据位序找字符串;

#include <iostream> using namespace std; const int MAXSIZE=100000; char str[MAXSIZE]; char in[MAXSIZE]; int l[26]; int len; int num; int g(int n) { int ret=1; for(int i=1;i<=n;++i) { ret*=i; } return ret; } int f() { int top=0,bot=1; for(int i=0;i<26;++i) { top+=l[i]; bot=bot*g(l[i]); } int ret=g(top)/bot; return ret; } int getStr(int pos) { if(pos==len) { return 0; } int ret=0; for(int i=0;i<in[pos-1]-'a';++i) { if(l[i]>0) { --l[i]; ret+=f(); ++l[i]; } } --l[in[pos-1]-'a']; ret+=getStr(pos+1); return ret; } int main() { memset(str,0,sizeof(str)); memset(in,0,sizeof(in)); memset(l,0,sizeof(l)); cin>>str>>in; len=strlen(str); for(int i=0;i<len;++i) { l[str[i]-'a']++; } cout<<getStr(1)+1<<endl; return 0; }

以上为根据字符串,找到它所在的字典序.

#include <iostream> using namespace std; const int MAXSIZE=100000; char str[MAXSIZE]; char out[MAXSIZE]; int l[26]; int len; int num; int g(int n) { int ret=1; for(int i=1;i<=n;++i) { ret*=i; } return ret; } int f() { int top=0,bot=1; for(int i=0;i<26;++i) { top+=l[i]; bot=bot*g(l[i]); } int ret=g(top)/bot; return ret; } bool getStr(int pos,int cur) { if(cur==len) { for(int j=0;j<26;++j) { if(l[j]) { out[cur-1] =j+'a'; } } cout<<out<<endl; return true; } else { int now=0; for(int i=0;i<26;++i) { if(l[i]>0) { l[i]--; now+=f(); if(now>=pos) { out[cur-1]=i+'a'; if(getStr(pos-(now-f()),cur+1)) { return true; } } l[i]++; } } return false; } } int main() { memset(str,0,sizeof(str)); memset(out,0,sizeof(out)); memset(l,0,sizeof(l)); cin>>str>>num; len=strlen(str); memset(l,0,sizeof(l)); for(int i=0;i<len;++i) { l[str[i]-'a']++; } if(!getStr(num,1)) { cout<<"false"<<endl; } return 0; }

以上为根据字典序,恢复字符串.

思想:

 有重集合的全排列公式:  (n1+n2+n3....nk)!

                                  --------------------

                                    n1!n2!n3!....nk!

k表示一共有几种字符,n1,n2,...nk 表示每种字符的数量.

通过这个公式可以计算出排列数,对于无重集合一样适用.

两个算法都是围绕这个公式与一种逐位考虑的思想,从字符串第一位,一位一位的确定,利用递归解决的问题.

具体思想不描述了,见算法竞赛入门经典P186页.