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

Ответ 1

Это расширенная и исправленная версия ответа Subhasis.

Формально проблема заключается в том, что для n-буквенного алфавита V и двух m-буквенных слов x и y, для которых существует такая перестановка p, что p (x) = y, определяет наименьшее число свопов ( перестановки, фиксирующие все, кроме двух элементов), состав которых q удовлетворяет q (x) = y. Предполагая, что n-буквенные слова являются отображениями из множества {1,..., m} в V и что p и q являются перестановками на {1,..., m}, действие p (x) определяется как состав p, за которым следует x.

Наименьшее количество свопов, состав которых равен р, может быть выражен через циклическое разложение р. Когда j ₁,..., j _k попарно различаются в {1,..., m}, цикл (j ₁... j _k) является перестановкой, которая отображает j _i на j _{я + 1} для я в {1,..., k - 1}, отображает j _k на j ₁ и отображает каждый другой элемент в себя. Перестановка p представляет собой композицию каждого отдельного цикла (j p (j) p (p (j))... j '), где j произвольно и p (j') = j. Порядок композиции не имеет значения, так как каждый элемент появляется точно в одном из составленных циклов. Цикл k-элементов (j ₁... j _k) можно записать как произведение (j ₁ j _k) (j ₁ j _{k - 1})... (j ₁ j ₂)) k - 1 цикл. В общем, каждая перестановка может быть записана как композиция m свопов за вычетом количества циклов, включающих его разложение цикла. Прямое индукционное доказательство показывает, что это оптимально.

Теперь мы доходим до сути ответа Subhasis. Экземпляры проблемы с азбукой соответствуют друг другу с эйлеровым (для каждой вершины, в градусах, равна -дегре) орграфов G с вершинами V и m дугами с меткой 1,..., m. Для j в {1,..., n} дуга, помеченная j, переходит от y (j) в x (j). Задача с точки зрения G состоит в том, чтобы определить, сколько частей может иметь разбиение дуг G на направленные циклы. (Так как G эйлерова, такое разбиение всегда существует.) Это связано с тем, что перестановки q такие, что q (x) = y находятся во взаимно однозначном соответствии с разбиениями следующим образом. Для каждого цикла (j ₁... j _k) q существует часть, направленный цикл которой состоит из дуг, помеченных j ₁,..., j _k.

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

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

@article{DBLP:journals/corr/GutinJSW14,
  author    = {Gregory Gutin and
               Mark Jones and
               Bin Sheng and
               Magnus Wahlstr{\"o}m},
  title     = {Parameterized Directed \$k\$-Chinese Postman Problem and \$k\$
               Arc-Disjoint Cycles Problem on Euler Digraphs},
  journal   = {CoRR},
  volume    = {abs/1402.2137},
  year      = {2014},
  ee        = {http://arxiv.org/abs/1402.2137},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Ответ 2

Вы можете построить строки "разности" S и S', то есть строку, которая содержит символы в разных положениях двух строк, например. для acbacb и abcabc это будет cbcb и bcbc. Скажем, это содержит n символов.

Теперь вы можете построить "граф перестановок" G, который будет иметь n узлы и ребро от i до j, если S[i] == S'[j]. В случае всех уникальных символов легко видеть, что требуемое количество свопов будет (n - количество циклов в G), которое можно обнаружить в O (n) времени.

Однако в случае, когда имеется любое количество повторяющихся символов, это сводится к задаче нахождения наибольшего числа циклов в ориентированном графе, который, я думаю, является NP-hard (например, проверьте: http://www.math.ucsd.edu/~jverstra/dcig.pdf).

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

• На каждом шаге найдите минимальный цикл длины в графе (например, Найдите цикл кратчайшей в ориентированном графе с положительными весами)
• Удалить его
• Повторяйте до тех пор, пока все вершины не будут покрыты.

Однако могут быть эффективные алгоритмы, использующие свойства вашего случая (единственное, о чем я могу думать, это то, что ваши графики будут K-partite, где K - количество уникальных символов в S). Удачи!

Изменить: Пожалуйста, обратитесь к Дэвиду за более полное и правильное объяснение проблемы.

Ответ 3

Сделайте поиск A * (см. http://en.wikipedia.org/wiki/A-star_search_algorithm для объяснения) для кратчайшего пути через график эквивалентных строк из одной строки в другой. Используйте расстояние Левенштейна /2 в качестве эвристической стоимости.

Ответ 4

Первое, на что нужно ответить, -

What is a mismatch ?

Несоответствие - это когда символы не соответствуют порядку.

When are characters out of order ?

Первое предположение: две строки являются взаимозаменяемыми.

Второе предположение: обе строки имеют одинаковую длину.

Таким образом, из-за порядка означает, что для символа i в первой строке конечно существует другой символ в позиции j во втором строка.

When are swaps required ?

Итак, для любого заданного индекса i, если символы в обеих строках не равны. Существует несоответствие. Сколько несоответствий? 2 несоответствия. Поскольку несогласованный символ из первой строки вызовет несоответствие во второй строке в другой позиции j. Таким образом, общее количество несоответствий всегда будет кратным 2.

Один своп корректирует положение в 2 символа. Таким образом, оптимальное количество несоответствий составляет половину общего числа несоответствий.

Вот пример кода.

public class CharacterMismatch {
    /**
     * Returns -1 if not possible
     * @param first
     * @param second
     * @return
     */
    public static int maxSwaps(char first[], char second[]) {
        if (first.length != second.length) {
            return -1;
        }
        int freqFirst[] = new int[Character.MAX_VALUE], freqSecond[] = new int[Character.MAX_VALUE];
        int len = first.length;
        for (int i = 0; i < len; ++i) {
            freqFirst[first[i]]++;
            freqSecond[second[i]]++;
        }

        for (int i = 0; i < len; ++i) {
            if (freqFirst[i] != freqSecond[i]) {
                return -1;
            }
        }

        //count mismatches. That is the minimal number of swaps required.
        int swaps = 0;
        for (int i = 0; i < len; ++i) {
            if (first[i] != second[i]) {
                swaps++;
            }
        }

        return swaps / 2;
    }

    public static void main(String[] args) {
        String first[] = { "aabbccdd", "abcc", "abccab" };
        String second[] = { "ddbbccaa", "accb", "abcabc"};

        for (int i = 0; i < first.length; ++i) {
            System.out.printf("%s %s => %d%n", first[i], second[i], maxSwaps(first[i].toCharArray(), second[i].toCharArray()));
        }
    }
}

Возвращает

aabbccdd ddbbccaa => 2
abcc accb => 1
abccab abcabc => 1

Сложность - это O (n).

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

Edit:

Извините, это работает только тогда, когда максимальное количество свопов для каждого несоответствующего символа не более одного.

Ответ 5

Структура данных хэш-карты (которая позволяет дубликаты) подходит для решения проблемы.

Пусть строка будет s1 и s2. Алгоритм выполняет итерацию по строке и всякий раз, когда обнаружено несоответствие, алгоритм отображает символ s1 в s2, т.е. char s1 в качестве ключа и char для s2, поскольку значение вставляется в Hash Map везде, где происходит несоответствие.

После этого инициализируйте результат как ноль.

Следующим шагом является то, что Hash Map не пуст, выполните следующие действия:

• Для любого ключа k найдите его значение v.
• Теперь используйте значение v в качестве ключа для поиска в Hash-карте, чтобы найти значение, если найденное значение равно k, а затем увеличивайте результат на 1 и удалите обе клавиши k и v из Hash-карты.
• Если найденное значение не равно k, то удалите ключ k из Hash-карты и увеличивайте результат.

содержит желаемый результат.