Блог пользователя T_C_D

Finding the nth Lexicographical String in a Dictionary
Автор T_C_D, история, 5 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      .

      → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить