Алгоритм / код расстояния редактирования строки анаграммы?

Есть две строки анаграммы S и P. Есть две основные операции:

  1. Поменяйте местами две соседние буквы, например, поменяйте местами «A» и «C» в BCCAB, стоимость равна 1.
  2. Поменять местами первую букву и последнюю букву в строке, стоимость равна 1.

Вопрос: Разработайте эффективный алгоритм, минимизирующий стоимость замены S на P.

Я попробовал жадный алгоритм, но нашел встречные примеры и считаю его неверным. Я знаю известное расстояние редактирования задачи DP, но я не получил формулу для этой.

Кто-нибудь может помочь? Идея и псевдокод были бы замечательными.


algorithm anagram
person Jin    schedule 04.01.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Интересно, будет ли http://en.wikipedia.org/wiki/A*_search_algorithm считаться эффективный? Для эвристики найдите наименьшее расстояние, которое должен пройти каждый символ, рассматривая строку как круг, и разделите сумму этих расстояний на два. В круге каждый персонаж должен участвовать в достаточном количестве обменов, чтобы перемещать его по одному шагу к месту назначения, и каждый обмен влияет только на двух персонажей, поэтому эта эвристика должна быть нижней границей требуемого количества обменов.

person mcdowella    schedule 04.01.2015

arrow_upward
0
arrow_downward

Без перестановки концов ответ прост: вы должны правильно получить первую и последнюю букву, и нет никакого способа «сохранить», сделав это позже; следовательно, для слова ai, где 0 <= i < n, вы должны "высветить" правильные a0 и an-1 на месте, а затем повторить для слово ai, где 1 <= i < n-1, пока не останется 0 или 1 букв.

С опцией обмена концами у вас остается гораздо более сложная проблема, поскольку есть два направления, в которых каждая буква может попасть в нужное место. По сути, у вас будет двудольный граф между исходным и целевым словом, и вы захотите найти соответствие, которое минимизирует сумму расстояний. Даже это на самом деле не алгоритм, поскольку каждый обмен перемещает две буквы, а не одну.

Суть в том, что вам, возможно, придется выполнить поиск, но, по крайней мере, вы можете ограничить поиск расстоянием без конца и подкачки.

person Juuso    schedule 08.07.2016
comment
Возможно, будет легче найти решение, если вы забудете о втором правиле и просто будете рассматривать строку как циклический буфер, где вы можете пузыриться «вокруг» в обоих направлениях - на самом деле просто другая ментальная модель... - person le_m; 08.07.2016