Мотивация : Разрабатывая инструменты для управления версиями данных, мы в конечном итоге изучили алгоритмы «различий» двух наборов целых чисел, предложив последовательность преобразований, которые переводят один набор целых чисел в другой. Мы смогли свести эту проблему к следующей очень естественной проблеме, которая, кажется, имеет соединения для редактирования расстояния, группировки путем замены и минимального общего строкового раздела .
Проблема : Нам дана строка, то есть последовательность букв, и наша цель состоит в том, чтобы гомогенизировать ее с минимальными затратами. То есть мы хотим переставить последовательность так, чтобы все одинаковые буквы были рядом друг с другом.
Единственная разрешенная операция - это подобрать подпоследовательность одинаковых букв и переместить эту подпоследовательность куда угодно, и это стоит мне 1 единицу.
Любая помощь, характеризующая сложность этой проблемы, будет высоко ценится!
Пример :
- aabcdab: вход
- bcd aa ab: после перемещения первого aa в положение сразу после «d»
- b bcdaaa: после перемещения трейлера b в первую позицию
Поскольку полученная строка является однородной, мы имеем стоимость 2.
Обратите внимание, что мы ничем не ограничены в отношении вывода: пока он однороден, нам не нужно обеспечивать какой-либо конкретный порядок.
источник
Посмотрите на количество изменений от одной буквы к другой в вашей строке, которые вы могли бы видеть в качестве меры для неоднородности строки. С каждым (полезным) ходом подпоследовательности вы уменьшаете это число на единицу, если перед подпоследовательностью, которой вы перемещаетесь, предшествуют две отдельные буквы. В противном случае вы уменьшите неоднородность на два.
Таким образом, для строки с k изменениями вам нужно не более k - l + 1 ходов, где l - количество различных букв в строке, потому что в конце l - 1 изменения останутся. Поскольку строка длиной n может содержать не более n-1 буквенных изменений, может потребоваться не более n - l ходов. Наименьшее возможное число - половина этого.
Таким образом, наилучшая стратегия заключается в поиске подпоследовательностей формы abbba и удалении bbb оттуда. Когда ничего не осталось, двигайся что угодно. Вы все еще можете попытаться выполнить те операции, которые создают новые ситуации abbba, но я думаю, что выигрыш будет очень небольшим. Поскольку в наихудшей из возможных стратегий (без глупых ходов, которые увеличивают неоднородность) используется не более, чем в два раза больше ходов, чем в оптимальном, малое, что вы можете получить, кажется, не имеет никакого разумного отношения к усилию, как ответ от isaacg с характеристикой как НП-хард подсказывает. Если, конечно, вы действительно только считаете количество операций перемещения и не заботитесь о времени, чтобы решить, какие шаги делать.
Поэтому в худшем случае это строка, в которой каждая буква отличается от своей предшественницы (и вы не получите никаких бонусов abbba). Здесь вам нужно количество операций, линейных по длине строки и практически равных этой длине.
В вашем примере у вас есть 5 -> 4 -> 3 изменения, а 3 равно количеству букв (4) минус 1.
Примечание: для алфавита размером только два, каждое движение, которое не перемещает префикс или суффикс строки, уменьшает неоднородность на два, и, следовательно, каждая последовательность разумных ходов является оптимальной.
источник