Сложность гомогенизации строки

10

Мотивация : Разрабатывая инструменты для управления версиями данных, мы в конечном итоге изучили алгоритмы «различий» двух наборов целых чисел, предложив последовательность преобразований, которые переводят один набор целых чисел в другой. Мы смогли свести эту проблему к следующей очень естественной проблеме, которая, кажется, имеет соединения для редактирования расстояния, группировки путем замены и минимального общего строкового раздела .

Проблема : Нам дана строка, то есть последовательность букв, и наша цель состоит в том, чтобы гомогенизировать ее с минимальными затратами. То есть мы хотим переставить последовательность так, чтобы все одинаковые буквы были рядом друг с другом.

Единственная разрешенная операция - это подобрать подпоследовательность одинаковых букв и переместить эту подпоследовательность куда угодно, и это стоит мне 1 единицу.

Любая помощь, характеризующая сложность этой проблемы, будет высоко ценится!

Пример :

  • aabcdab: вход
  • bcd aa ab: после перемещения первого aa в положение сразу после «d»
  • b bcdaaa: после перемещения трейлера b в первую позицию

Поскольку полученная строка является однородной, мы имеем стоимость 2.

Обратите внимание, что мы ничем не ограничены в отношении вывода: пока он однороден, нам не нужно обеспечивать какой-либо конкретный порядок.

Адитья Парамесваран
источник

Ответы:

6

Эта проблема является NP-полной, путем сокращения от минимального набора удара .

В минимуме ударяя множество, мы дали Вселенной, и набор множеств такое , что . Цель состоит в том, чтобы найти наименьшего размера, такого что такого что .S сек S , ˙s U H U s S , ч H H sUSsS,sUЧАСUsS,часЧАСчасs

Сокращение заключается в следующем:

  • Строка выглядит следующим образом: Для каждого элемента будет два символа строки . Между этими символами будет символ для каждого такой что . Между парами с, будут уникальные символы, которые не повторяются в строке.u s s S u s u UUU's'sSUsU'

  • Чтобы гомогенизировать строку, символ должен быть перемещен раз, для каждого . Кроме того, для каждой и , то символ должен быть перемещен один раз, если каждый между парой был перемещен в другом месте.| с | - 1 s u u s u s'|s|-1sUU's'U'

  • Поэтому, чтобы минимизировать количество ходов, необходимых для гомогенизации строки, мы хотим максимизировать количество , чтобы каждый был перемещен в другое место. Объекты где не были перемещены в другое место, должны вместе содержать для каждого , поэтому они должны для набора удара. Кроме того, любой такой набор ударять может служить заканчивающиеся местоположениями с, перемещая каждый в , который ударяет его.U's'U's's'sSs'sU

  • Таким образом, число ходов для гомогенизации этой строки равногде - минимальный ударный набор.Σ|s|+|ЧАС*|ЧАС*

Поскольку минимальный ударный набор NP-Hard, оптимально гомогенизирует струну. Поскольку ходы формируют свидетеля, он NP-завершен.

isaacg
источник
Это элегантное сокращение - спасибо!
Адитья Парамесваран
2

Посмотрите на количество изменений от одной буквы к другой в вашей строке, которые вы могли бы видеть в качестве меры для неоднородности строки. С каждым (полезным) ходом подпоследовательности вы уменьшаете это число на единицу, если перед подпоследовательностью, которой вы перемещаетесь, предшествуют две отдельные буквы. В противном случае вы уменьшите неоднородность на два.

Таким образом, для строки с k изменениями вам нужно не более k - l + 1 ходов, где l - количество различных букв в строке, потому что в конце l - 1 изменения останутся. Поскольку строка длиной n может содержать не более n-1 буквенных изменений, может потребоваться не более n - l ходов. Наименьшее возможное число - половина этого.

Таким образом, наилучшая стратегия заключается в поиске подпоследовательностей формы abbba и удалении bbb оттуда. Когда ничего не осталось, двигайся что угодно. Вы все еще можете попытаться выполнить те операции, которые создают новые ситуации abbba, но я думаю, что выигрыш будет очень небольшим. Поскольку в наихудшей из возможных стратегий (без глупых ходов, которые увеличивают неоднородность) используется не более, чем в два раза больше ходов, чем в оптимальном, малое, что вы можете получить, кажется, не имеет никакого разумного отношения к усилию, как ответ от isaacg с характеристикой как НП-хард подсказывает. Если, конечно, вы действительно только считаете количество операций перемещения и не заботитесь о времени, чтобы решить, какие шаги делать.

Поэтому в худшем случае это строка, в которой каждая буква отличается от своей предшественницы (и вы не получите никаких бонусов abbba). Здесь вам нужно количество операций, линейных по длине строки и практически равных этой длине.

В вашем примере у вас есть 5 -> 4 -> 3 изменения, а 3 равно количеству букв (4) минус 1.

Примечание: для алфавита размером только два, каждое движение, которое не перемещает префикс или суффикс строки, уменьшает неоднородность на два, и, следовательно, каждая последовательность разумных ходов является оптимальной.

Питер Лейпольд
источник
Вы утверждаете, что перемещение может уменьшить количество изменений максимум на 2, но на самом деле это может уменьшить количество изменений до 3. Например, преобразование «aabcabc» в «aaabbcc» путем перемещения первой подстроки «bc» в середина второй подстроки "bc" приводит к уменьшению количества изменений в строке с 5 до 2.
Михаил Рудой
Привет, @MikhailRudoy. В вопросе говорится, что операция «подобрать подпоследовательность одинаковых букв», поэтому bc не разрешен, насколько я понимаю.
Питер
Я полностью пропустил эту деталь. Вы правы в этом случае.
Михаил Рудой
Петр прав: эти шаги не разрешены.
Адитья Парамесваран
Re: остальная часть ответа - действительно, эти наблюдения re: нижние границы, оптимальность случая размера 2 алфавита и эвристика для того, что делать в любой момент, являются ценными. Поскольку любое движение в худшем случае приносит пользу только той последовательности букв, а в лучшем случае объединяет не более двух последовательностей букв, как в вашем abbba, 2-приближение кажется естественным.
Адитья Парамесваран