Стыдно признаться, вчера, когда при выполнении лабораторной мне понадобилось найти обратную перестановку, то выяснилось, что я напрочь забыл, как это делается… Пошел за помощью к Яндексу. И, удивительно, но он мне не смог помочь найти алгоритм вычисления обратной перестановки! Почесав тыковку, пришлось сочинять его самому. Все оказалось достаточно просто и логично, хотя неприятный осадок, что у меня это вылетело из памяти, остался…
На всякий случай напомню, следуя за википедией, по которой:
«В комбинаторике перестановка — это упорядоченный набор, который числу 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 – вектор с обратной перестановкой
В коде это выглядит чуть сложнее:
for (int j = 0; j < size; j++)
{
op[i] += p[p[p[j]-1]-1]-1];
}PS: этот небольшой пост писался специально для таких же забывчивых, как я, чтобы теперь у нас была возможность спокойно найти «как вычислить обратную перестановку к заданной» в Яндексе и Google.
Полезная статья? Их будет больше, если вы поддержите меня!
Архив комментариев
2 комментария из прежней версии блога. Архив закрыт для новых ответов.
Извините, но мне кажется вы ошибаетесь. Обратная перестановка вычисляется следующим образом:
vector inverse(const vector& p) {
vector result(p.size);
for(int i=0; i<p.size(); i++)
result[p[i]] = i;
return result
}
Александр, Вам кажется :) И мой и ваш код дают абсолютно верный ответ с одной только разницей: мой код вычисляет перестановку в «человеческом» стиле, т.е. индексы в ней идут от 1, а Ваш — в «сишном», т.е. индексы начинаются от 0.