алгоритм транспонирования строк

Question

Предположим, есть две строки:

String s1= "MARTHA"
String s2= "MARHTA"

здесь мы обмениваемся позициями T и H. Мне интересно написать код, который подсчитывает, сколько изменений необходимо преобразовать из одной строки в другую.

Answer 1

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

Answer 2

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

Первый шаг алгоритма - убедиться, что две строки действительно эквивалентны по своему содержанию символов. Это может быть сделано за линейное время с использованием хеш-таблицы (или фиксированного массива, который охватывает весь алфавит). Если это не так, то s2 не может рассматриваться как перестановка s1, и «количество свопов» не имеет значения.

На втором шаге подсчитывается минимальное количество обменов, необходимое для преобразования s2 в s1. Это может быть сделано путем проверки перестановки p, которая соответствует преобразованию из s1 в s2. Например, если s1 = "abcde" и s2 = "badce", то p = (2,1,4,3,5), что означает, что позиция 1 содержит элемент # 2, позиция 2 содержит элемент # 1 и т. Д. Перестановка может быть разбита на циклов перестановки в линейном времени. Циклы в этом примере (2,1) (4,3) и (5). Минимальное количество свопов - это общее количество свопов, необходимое для цикла. Цикл длины k требует k-1 перестановок, чтобы «исправить это». Следовательно, число перестановок равно N-C, где N - длина строки, а C - количество циклов. В нашем примере результат равен 2 (своп 1,2, а затем 3,4).

Теперь есть две проблемы, и я думаю, что слишком устал, чтобы решать их прямо сейчас:)

1) Мое решение предполагает, что ни один символ не повторяется, что не всегда так. Некоторая корректировка необходима для правильного расчета количества свопов.

2) Моя формула # MinSwaps = N-C нуждается в доказательстве ... Я не нашел его в сети.

Answer 3

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

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

Если вы не хотите эффективно это делать, а просто подсчитываете количество обменов, используйте битовый массив, в котором у вас есть 1 для каждого правильно расположенного символа и0 в противном случае.Вы закончите, когда каждый бит будет 1.