Количество свопов в перестановке

Есть ли эффективный алгоритм (эффективный с точки зрения большой записи O), чтобы найти число свопов для преобразования перестановки P в подстановку I? Сделки не обязательно должны находиться на соседних элементах, но на любых элементах.

Итак, например:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5)
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)

Одна идея - написать такой алгоритм:

int count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) { // could be permuted multiple times
        std::swap(P[P[i]], P[i]);
        // look where the number at hand should be
    }
}

Но мне не совсем понятно, действительно ли это завершено или найдет правильное количество свопов. Он работает над приведенными выше примерами. Я попытался создать все перестановки на 5 и на 12 номеров, и он всегда заканчивается на них.

Эта проблема возникает в числовой линейной алгебре. В некоторых матричных разложениях используется поворот, который эффективно свопит строку с наибольшим значением для следующей строки, которой нужно манипулировать, чтобы избежать деления на небольшие числа и улучшить численную стабильность. Некоторые декомпозиции, такие как декомпозиция LU, могут впоследствии использоваться для вычисления матричного определителя, но знак детерминанта декомпозиции противоположен признаку исходной матрицы, если число перестановок нечетное.

EDIT. Я согласен, что этот вопрос похож на Подсчет смежных свопов, необходимых для преобразования одной перестановки в другую. Но я бы сказал, что этот вопрос более фундаментален. Преобразование перестановки из одного в другое можно преобразовать в эту проблему, инвертируя целевую перестановку в O (n), составив перестановки в O (n), а затем найдя количество свопов оттуда к идентификатору. Решение этого вопроса путем явного представления тождества как другой перестановки кажется субоптимальным. Кроме того, у другого вопроса до вчерашнего дня было четыре ответа, в которых только один (по | \/| ad) был, по-видимому, полезен, но описание метода казалось неопределенным. Теперь пользователь lizusek предоставил ответ на мой вопрос. Я не согласен с тем, что этот вопрос повторяется как дубликат.

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

Ответы

Ответ 1

Я считаю, что ключ должен думать о перестановке в терминах декомпозиции цикла.

Это выражает любую перестановку как произведение непересекающихся циклов.

Основные факты:

  • Подкачки элементов в двух непересекающихся циклах производят один более длинный цикл
  • Перемещение элементов в одном цикле приводит к меньшему циклу
  • Требуется число перестановок n-c, где c - число циклов в разложении

Ваш алгоритм всегда меняет элементы в одном цикле, поэтому правильно подсчитывает количество необходимых свопов.

При желании вы также можете сделать это в O (n), вычислив разложение цикла и вернув n за вычетом количества найденных циклов.

Вычисление разложения цикла может быть выполнено в O (n), начиная с первого node и после перестановки до тех пор, пока вы не вернетесь к началу. Отметьте все посещенные узлы, затем начните снова при следующем нерассмотренном node.

Ответ 2

Я считаю, что верно следующее:

Если S(x[0], ..., x[n-1]) - минимальное количество свопов, необходимых для преобразования x в {0, 1, ..., n - 1}, то:

  • Если x[n - 1] == n - 1, то S(x) == S(x[0],...,x[n-2]) (т.е. отрезать последний элемент)
  • Если x[-1] != n - 1, тогда S(x) == S(x[0], ..., x[n-1], ..., x[i], ... x[n-2]) + 1, где x[i] == n - 1.
  • S({}) = 0.

Это говорит о простом алгоритме вычисления S(x), который работает в O(n) времени:

int num_swaps(int[] x, int n) {
  if (n == 0) {
    return 0;
  } else if (x[n - 1] == n  - 1) {
    return num_swaps(x, n - 1);
  } else {
    int* i = std::find(x, x + n, n - 1);
    std::swap(*i, x[n - 1])
    return num_swaps(x, n - 1) + 1;
  }
}