JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
question about "Finding Lexicographically Kth string in a set" recipe | Reply
Hi I would like to post this post in this topic : http://apps.topcoder.com/forums/?module=Thread&threadID=643516&start=0 but that are closed. So I have to open a new thread, for my question (sry)..

Thanks for this article!

I don't understand this part:

- Sometimes the problem goes a step ahead and defines the set all of strings of length <= n and you are asked to find the lexicographically Kth string ie
S = { S(1), S(2) .... S(n) }
In that case if t[len] denote the total number of strings of length len, iterate over len subtracting from K as long as K > t[len]. After this K denotes the ordinal number in the set S(len). Ie We found the target strings length and ordinal number. We proceed as given in solution, call recurse(len, K)
For(len,1,n)
    For(j,0,m-1)
      t[len] += d[len,j]
   For(len,1,n)
   {
    if(K > t[len])
      K -= t[len];
    else
      break;     
   }
   
   recurse(len,K); 


I think if I follow your pseudocode then I think "b" is lexicographivcally less than "ab"?

So I would solve it in this way (try to follow your style):

For(j,0,m-1)
  For(len,1,n)
  {
    if(len>1)
      t[len,j]=t[len-1,j];
    else
      t[1,j]=1;
  }
//t[len,j] contains the number that words start with j and no longer than len     
 
while(K && len)
{
  for(j,0,m-1)
  {
    if(K>=t[len,j])
      K-=t[len,j];
    else
      break; 
  }
  answer += (char)('a'+j);
  --len;
}
 


Maybe I misunderstand the example, could you help me what?
RSS