T_C_D's blog

Finding the nth Lexicographical String in a Dictionary
By T_C_D, history, 21 month(s) ago, In English

Suppose i have a dictionary of an alphabet D (|D|>1) and i have an integer n (n between 1 and 1e18). I want to find the nth lexicographical string in this dictionary. How can I solve this problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
21 month(s) ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Suppose there are $$$x$$$ distinct characters, then we can simply transform $$$n$$$ into base $$$x$$$ to get the answer.

→ Reply
  • »
    »
    20 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    let D = {A,B}. let's say I want to find 2nd (=x) number in this dictionary. If I convert '2' to base 2 then we get '10'. Now how do we generate the string ?

    → Reply
    • »
      »
      »
      20 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      .

      → Reply
    • »
      »
      »
      20 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      As far as I understand bases, 1 and 0 are the indexes. The indexes also represent the weights, hence lexicography. So the string corresponding to 10 is BA.

      → Reply
»
20 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

walk on A-ary trie by holding subtree size. Where A is Alphabet size

→ Reply
»
20 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If this problem is about finding the nth lexicographical string, then the answer is character A n times, where A is the smallest lexicographical. I think they intended for the sequence to be sorted by length, and only then lexicographically. Then you can first find its length, denote it as L, then find nth lexicographical string of length L (n will be different after canceling out every string with size < L). I can share the code if you want

→ Reply