Нахождение обратной перестановки

{lang: 'ru'}

Стыдно признаться, вчера, когда при выполнении лабораторной мне понадобилось найти обратную перестановку, то выяснилось, что я напрочь забыл, как это делается… Пошел за помощью к Яндексу. И, удивительно, но он мне не смог помочь найти алгоритм вычисления обратной перестановки! Почесав тыковку, пришлось сочинять его самому. Все оказалось достаточно просто и логично, хотя неприятный осадок, что у меня это вылетело из памяти, остался…

На всякий случай напомню, следуя за википедией, по которой:

«В комбинаторике перестановка — это упорядоченный набор, который числу i ставит соответствие i-й элемент из набора.»

Соответственно,

«обратная перестановка – это такая перестановка p^-1, которая после применения к исходной перестановке p дает единичную перестановку перестановку e: p^-1 * p = e»

Т.е. если исходная перестановка равна (3,1,4,2,5), то обратной к ней будет (2,4,1,3,5).

А после вычисления (3,1,4,2,5) (2,4,1,3,5) получится (1,2,3,4,5), или единичная перестановка.

Приведу еще один пример. Текстовый:

Пусть дан исходный текст «abc»


и дана перестановка (312)

После применения перестановки, текст трансформируется в «cab»

Для того, чтобы вернуть его в исходное состояние, необходимо применить перестановку (2,3,1), после которой перед нами будет вновь «abc»

А теперь, вернемся непосредственно к теме поста. Вот как нужно вычислять перестановку, обратную данной:

op[i]=p[ p [ p [ i ] ] ]

где p – вектор заданной перестановки, op – вектор с обратной перестановкой

В коде это выглядит чуть сложнее:

PS: этот небольшой пост писался специально для таких же забывчивых, как я, чтобы теперь у нас была возможность спокойно найти «как вычислить обратную перестановку к заданной» в Яндексе и Google.


Полезная статья? Их будет больше, если вы поддержите меня!


  • Pingback: Паради()

  • Александр

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

    vector inverse(const vector& p) {
    vector result(p.size);
    for(int i=0; i<p.size(); i++)
    result[p[i]] = i;
    return result
    }

  • Rossky

    Александр, Вам кажется :) И мой и ваш код дают абсолютно верный ответ с одной только разницей: мой код вычисляет перестановку в «человеческом» стиле, т.е. индексы в ней идут от 1, а Ваш — в «сишном», т.е. индексы начинаются от 0.