Author |
Topic: position of string in dictionary (Read 1856 times) |
|
witee
Newbie
Posts: 48
|
 |
position of string in dictionary
« on: Aug 27th, 2010, 5:33am » |
 Quote  Modify
|
A dictionary consists of words having the restriction that c[i] > c[i-1]. i.e character at ith positionis lexicographicaly greater than than character at i-1th position. eg abcd
given a string how do we find it's position in the dictionary?
eg a = position 1 , ab = position 27
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
|
Re: position of string in dictionary
« Reply #1 on: Aug 27th, 2010, 11:00pm » |
Quote Modify
|
An unoptimized implementation -
public static long computePosition(char start, char end, String value) {
int MAX = 26;
List<Character> alphabets = new ArrayList<Character>(MAX);
for (char c = start; c <= end; c++) {
alphabets.add(c);
}
int len = value.length();
long sum = 0;
for (int i = 1; i <= len - 1; i++) {
sum += nChooseK(alphabets.size(), i);
}
for (int i = 0; i < len; i++) {
int position = alphabets.indexOf(value.charAt(i));
if (position == -1) {
throw new IllegalArgumentException("Invalid String!");
}
for (int j = 0; j < position; j++) {
sum += nChooseK(alphabets.size() - 1, len - i - 1);
alphabets.remove(0);
}
alphabets.remove(0);
}
return sum + 1;
}
Gives :-
z = 26, ab = 27
yz = 351, abc = 352
xyz = 2951, abcd = 2952
wxyz = 17901, abcde = 17902
vwxyz = 83681, abcdef = 83682
uvwxyz = 313911, abcdefg = 313912
tuvwxyz = 971711, abcdefgh = 971712
stuvwxyz = 2533986, abcdefghi = 2533987
rstuvwxyz = 5658536, abcdefghij = 5658537
qrstuvwxyz = 10970271, abcdefghijk = 10970272
pqrstuvwxyz = 18696431, abcdefghijkl = 18696432
|
| « Last Edit: Aug 27th, 2010, 11:01pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
jack_alyz
Newbie
Posts: 8
|
|
Re: position of string in dictionary
« Reply #2 on: Sep 9th, 2010, 1:54am » |
Quote Modify
|
This will be exactly inverse of finding kth permutation and would be easy to understand in recursive.
calculate matrix M, where M[i][j] = number of permutation possible of length i, starting with jth character.
| hidden: |
This would be easy to calculate in bottomup fashion in O(mn) where n=alphabet length, m=permutation length (string in query)
take k = 0
for each char at ith position
for 0<= j < char[i]-'a'
k+= M[n-i-1][j]
return k; |
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: position of string in dictionary
« Reply #3 on: Sep 14th, 2010, 8:57am » |
Quote Modify
|
Objection, my honor! Lexicographical order would be as follows:
a = 1
ab = 2
abc = 3
...
abc...wxy = 25
abc...wxyz = 26
abc...wxz = 27
abc...wy = 28
abc...wyz = 29
abc...wz = 30
abc...u = 31
Which is a bit messier to compute, I think.
|
| « Last Edit: Sep 14th, 2010, 8:58am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print