Блог пользователя egor.okhterov

Автор egor.okhterov, история, 8 лет назад, перевод, По-русски

Мы порождаем все триплеты используя алфавит из 26 английских букв (A = {a, b, c, ..., z}):
A3 = A × A × A = 
{
  (a, a, a), 
  (a, a, b), 
  (a, a, c), 
    ..., 
  (a, a, z), 
  (b, a, a), 
    ..., 
  (z, z, y), 
  (z, z, z), 
}

|A3| = 263 = 17576

  • Если мы попытаемся слить триплеты aaa и bbb, то нам придётся прикрепить bbb к концу строки aaa, так как они не перекрываются:
    merge(aaa, bbb) = aaabbb

  • Но если мы сливаем строку aaa со строкой aab, то мы получим результат меньшей длины:
    merge(aaa, aab) = aaab

В лучшем случае, если нам получится всегда делать слияния второго типа, то для каждого триплета (кроме первого) мы будем просто удлинять результирующую строку на 1 символ. Всего у нас есть 17576 триплетов, так что мы добавим к результирующей строке 17575 символов. В результате этих добавлений финальная строка, содержащая все возможные триплеты, будет иметь длину 17575 + 3 = 17578.

В худшем случае мы всегда будем делать операцию слияния первого типа, что приведёт к результирующей строке длины 17576 * 3 = 52728.

Лучший результат находится где-то в интервале [17578, 52728].

Как же нам скомбинировать все триплеты, чтобы получить строку минимальной длины?


Картинка для привлечения внимания.

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем egor.okhterov (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where is this problem from?

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

    It is my problem inspired by Symbolic Sequence.

    For me it looks like the problem is pretty foundational, but I couldn't google neither the problem nor the solution. The closest problem that I found is the problem of assembling human genome, but again it is pretty different from what I am looking for.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      I believe this is exactly what you want.

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

        Thank you!
        But how did you google it? :)

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

          I just happen to know some old problem that is named after this sequence and asks to find exactly it.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Эхх что за времена пошли два русских друг с другом на английском общаются.
            UPD И у самого страна Америка )))))))