wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> position of string in dictionary
        
(Message started by: witee on Aug 27^th, 2010, 5:33am)

Title: position of string in dictionary
Post by witee on Aug 27^th, 2010, 5:33am

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

Title: Re: position of string in dictionary
Post by TenaliRaman on Aug 27^th, 2010, 11:00pm

An unoptimized implementation -
[hide]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;
}[/hide]

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

Title: Re: position of string in dictionary
Post by jack_alyz on Sep 9^th, 2010, 1:54am

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.
[hideb]
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;[/hideb]

Title: Re: position of string in dictionary
Post by Grimbal on Sep 14^th, 2010, 8:57am

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.