Essays/Self-Downgrading Permutations
A permutation p is self-downgrading if p-:\:p . The phrase sdp n computes all the self-downgrading permutations of order n .
sdp=: 3 : 0
if. (1>:y)+.2<:4|y do. i.(1>:y),y return. end.
r=. 4|y
m=. y-1
p=. <.-:y
k=. (>.-:y)+i.-<:p
e=. ((i.y)-.0,m,r$p) -."1 k,.m-k
t=. ,/ k,."_1~ (k~:/|.k) #^:_1"1"_1 ((<.-:y-4)}."1 sdp y-4+r) {"_ 1 e
(, |."1@|.) (|."1 m-t),.(-.r)}."1 p,.t
)
The algorithm is from E.E. McDonnell, Magic Squares and Permutations, APL Quote Quad, Volume 7, Number 3, 1976-09, and derives by observing that a choice for the first element of a row immediately determines three other elements of that row. We first generate the upper right corner (local name t in sdp ), whence the full result obtains easily.
sdp&.> 4 5 ,: 8 9 ┌───────────────┬─────────────────┐ │1 3 0 2 │1 4 2 0 3 │ │2 0 3 1 │3 0 2 4 1 │ ├───────────────┼─────────────────┤ │1 7 3 5 2 4 0 6│1 8 3 6 4 2 5 0 7│ │1 7 4 2 5 3 0 6│1 8 5 2 4 6 3 0 7│ │2 3 7 6 1 0 4 5│2 3 8 7 4 1 0 5 6│ │2 4 7 1 6 0 3 5│2 5 8 1 4 7 0 3 6│ │3 2 6 7 0 1 5 4│3 2 7 8 4 0 1 6 5│ │3 5 1 7 0 6 2 4│3 6 1 8 4 0 7 2 5│ │4 2 6 0 7 1 5 3│5 2 7 0 4 8 1 6 3│ │4 5 1 0 7 6 2 3│5 6 1 0 4 8 7 2 3│ │5 3 0 6 1 7 4 2│6 3 0 7 4 1 8 5 2│ │5 4 0 1 6 7 3 2│6 5 0 1 4 7 8 3 2│ │6 0 3 5 2 4 7 1│7 0 3 6 4 2 5 8 1│ │6 0 4 2 5 3 7 1│7 0 5 2 4 6 3 8 1│ └───────────────┴─────────────────┘
If perm n are all the permutations of order n , the phrase (#~ ] -:"1 \:"1) perm n is equivalent to sdp n , but requires space (and time) exponential in the size of the desired result.
perm=: i.@! A. i. f=: (#~ ] -:"1 /:"1) @ perm (f -: sdp)"0 i.9 1 1 1 1 1 1 1 1 1
sdpcheck has the same argument and result as sdp , but incorporates checks:
sdpcheck=: 3 : 0
z=. sdp y
assert. 2=#$z
assert. y={:$z
assert. (i.y) -:"1 /:~"1 z
assert. z -: /:~ z
assert. z -: \:"1 z
)
The number of self-downgrading permutations can be computed as follows:
nsdp=: (2 > 4 | ]) * (!@+: % !)@<.@(4x %~ ]) nsdp"0 i.20 1 1 0 0 2 2 0 0 12 12 0 0 120 120 0 0 1680 1680 0 0 nsdp"0 i.20 1 1 0 0 2 2 0 0 12 12 0 0 120 120 0 0 1680 1680 0 0
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. Portions of the text previously appeared as part of Some Uses of { and } by Roger Hui, APL87 Conference Proceedings, May 10-14, 1987.