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