Essays/Self-Downgrading Permutations

From J Wiki
Jump to: navigation, search

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


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.