Permalex
Given a string of characters, we can permute the individual characters to make new strings. If we can impose an ordering on the characters (say alphabetic sequence), then the strings themselves can be ordered and any given permutation can be given a unique number designating its position in that ordering. For example the string `acab' gives rise to the following 12 distinct permutations:| Permalex |
Thus the string `acab' can be characterised in this sequence as 5.
Write a program that will read in a string and determine its position in the ordered sequence of permutations of its constituent characters. Note that numbers of permutations can get very large; however we guarantee that no string will be given whose position is more than
.Input and Output
Input will consist of a series of lines, each line containing one string. Each string will consist of up to 30 lower case letters, not necessarily distinct. The file will be terminated by a line consisting of a single #.Output will consist of a series of lines, one for each line of the input. Each line will consist of the position of the string in its sequence, right justified in a field of width 10.
Sample input
bacaa abc cba #
Sample output
15
1
6
permutation
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;
string S;
vector<int>prime;
int base[50],cur[50];
int notp[30];
void getP(){
notp[0]=notp[1]=1;
int b;
rep(i,30)
if(!notp[i]){
prime.push_back(i);
if(DBG)printf("%d\n",i);
for(int b=i*2;b<30;b+=i)notp[b]=1;
}
}
void getEle(int c){
int a;
REP(i,2,c+1){
a=i;
rep(j,prime.size()){
while(a%prime[j]==0)a/=prime[j],base[prime[j]]++;
if(a==1)break;
}
}
}
void getCur(int c){
int a;
REP(i,2,c+1){
a=i;
rep(j,prime.size()){
while(a%prime[j]==0){
a/=prime[j];
if(base[prime[j]])base[prime[j]]--;
else cur[prime[j]]++;
}
if(a==1)break;
}
}
}
int getN(string s,int a,int b){
int cnt[26];
memset(cnt,0,sizeof(cnt));
memset(cur,0,sizeof(cur));
REP(i,a,b)cnt[s[i]-'a']++;
rep(i,26)if(cnt[i]>1)getEle(cnt[i]);
getCur(b-a);
int c=1;
REP(i,2,32)if(cur[i])c*=int(pow(i,cur[i])+0.5);
if(DBG)printf("getN: %s\n",s.c_str());
return c;
}
void getNum(){
int c=0;
char d;
bool add[256];
string s;
rep(i,S.size()-1){
memset(add,0,sizeof(add));
REP(j,i+1,S.size())
if(S[j]<S[i]&&!add[S[j]]){
s=S;
add[s[j]]=1;
d=s[i],s[i]=s[j],s[j]=d;
c+=getN(s,i+1,s.size());
}
}
printf("%10d\n",c+1);
}
int main(){
getP();
while(cin>>S){
if(S[0]=='#')break;
getNum();
}
}
. Each solution will consist of 8 numbers. Each of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated by the order in which the 8 numbers are printed. That is, the first number represents the ROW in which the queen is positioned in column 1; the second number represents the ROW in which the queen is positioned in column 2, and so on.
8 representation of each solution is shown below.
chessboard such that no Queen can take another Queen. Jan Timman (a famous Dutch chessplayer) wants to know the maximum number of chesspieces of one kind which can be put on an 
board with a certain size such that no piece can take another. Because it's rather difficult to find a solution by hand, he asks your help to solve the problem.
) and n ( 
), meaning the number of rows and the number of columns or the board.
. A pair of this form shows that computeri and computerj get interconnected.