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
```