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.