Расстояние между строками, только транспонирование

Возможный дубликат:
Подсчет свопов, необходимых для преобразования одной перестановки в другую

Я ищу алгоритм, который подсчитывал бы какое-то расстояние между строками, где разрешена только операция перестановки двух соседних символов. Например:
string1: "mother"
string2: "motherh"
Distance: 2 (сначала поменяйте местами "h" на "e" и получите "motehr", а затем "h" на " r" в результате получается "motherh")
Я знаю, что расстояние Дамерау-Левенштейна очень похоже на эту задачу, но требует много памяти (мне бы хотелось, чтобы оно работало довольно быстро со словами до 1 000 000 символов) . Я уже написал это:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    }
}
cout << amo << endl;`

Строки представлены в виде char[n], где n — их длина. Я совершенно уверен, что есть способ сделать это быстрее, и я был бы очень благодарен, если кто-нибудь скажет мне, как это сделать, или напишет исходный код (лучше всего будет Java/Python/C++, но все будет отлично).

P.S. Извините за языковые ошибки, я не англичанин и еще не освоил этот язык.


string algorithm dynamic-programming edit-distance levenshtein-distance
person Mateusz    schedule 25.10.2011    source источник
comment
Не так давно спросили и ответили: /7797540/некоторые-перестановки-с-бсортировкой/   -  person IVlad    schedule 25.10.2011

Ответы (1)


arrow_upward
5
arrow_downward

По сути, вы запрашиваете алгоритм редактировать расстояние, но разрешаете только транспонирование ( ака подкачка, переворачивание) операция. В книге «Введение в алгоритмы» вы найдете подсказки для реализации операции переворота, это одна из задач в конце главы о динамическом программировании. Кроме того, в книге «Руководство по разработке алгоритмов» в главе о динамическом программировании есть полная реализация алгоритма расстояния редактирования на языке C — без операции транспонирования (опять же, это одно из предложенных упражнений в конце главы). ).

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

То есть, если вам нужно только изменить distance . Если вам нужны фактические операции редактирования, вы застряли с использованием пространства O (mn) для восстановления решения if с использованием динамического программирования. Однако вы можете уменьшить пространство до O(min{m,n}) и восстановить фактические операции редактирования, используя алгоритм Хиршберга.

person Óscar López    schedule 25.10.2011
comment
Это был бы лучший ответ, если бы читателю не требовалось покупать или владеть несколькими учебниками по информатике! - person Nick Johnson; 26.10.2011
comment
Библиотеки действительно существуют... - person Óscar López; 26.10.2011
comment
Это ограниченный случай расстояния редактирования, и на самом деле более простой. Вам не нужен полный алгоритм O (mn), на самом деле это можно сделать за O (n log n) с сортировкой слиянием, см. связанный ответ в дублирующем закрытом окне. Это тау-расстояние Кендалла. - person jrouquie; 03.12.2018