Essays/Inverse Permutation

Compute the inverse q of permutation vector p such that q{p is the identity permutation i.#p .

   ] p=: ?.~ 23
4 22 16 15 18 14 7 8 0 21 3 13 20 9 11 19 6 17 2 5 1 10 12
   q=: 8 20 18 10 0 19 16 6 7 13 21 14 22 11 5 3 2 17 4 15 12 9 1
   q{p
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

A few ways of computing the inverse are presented.

Grade Up

(/:p){p sorts p and sorting a permutation vector results in the identity. That is, /:p computes the inverse of p .

   (/:p){p
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
   /: p
8 20 18 10 0 19 16 6 7 13 21 14 22 11 5 3 2 17 4 15 12 9 1

Index Of

If i e. p , then i=(p i. i){p . Therefore (i.#p)=(p i. i.#p){p and p i. i.#p is the inverse of p .

(i. i.@#) p

Amend

If q=: p}~i.#p then (i{q) = p i. i for i e. i.#p . That is, q = p i. i.#p and is exactly the previous case (Index Of).

p}~i.#p

Boolean Matrices

There is an isomorphism between integer permutation vectors and boolean permutation matrices under {= and i."1&1 . Therefore:

|: &. ({=) p
%. &. ({=) p

Cycles

The inverse of a single cycle is the reverse of the cycle elements, and C. p produces disjoint cycles, whence the inverse of a permutation obtains by reversing each of its cycles.

|.&.>&.C. p

---

See also

• Permutations
• Inverse Permutation
• Permutation Index
• Self-Upgrading Permutations
• Self-Downgrading Permutations
• Symmetric Array
• Symmetries of the Square
• Cayley's Theorem
• N Queens Problem

---

Contributed by Roger Hui.