A permutation p is self-upgrading if p-:/:p . The phrase sup n computes all the self-upgrading permutations of order n .

```sup=: 3 : 0
if. 1>:y do. i.1,y return. end.
t=. sup y-1
x=. (({."1 t)i.1){.t   NB. x=. 0,.1+sup y-2
k=. }.i.y
(0,.1+t) , ,/ k ,."_1 ((*+/\"1)-.=k) {"1"_1 x {"_ 1 (i.y)-."1 0 k
)
```

The algorithm is due to H.A. Rothe as described by E.E. McDonnell, Magic Squares and Permutations, APL Quote Quad, Volume 7, Number 3, 1976 9. In words, the rows in sup n whose first element is 0 , are form by prefixing 0 to 1+sup n-1 ; the rows whose first element is non-zero k has 0 in column k , the other columns are (sup n-2){(i.n)-.k,0 .

```   sup 3
0 1 2
0 2 1
1 0 2
2 1 0
sup 4
0 1 2 3
0 1 3 2
0 2 1 3
0 3 2 1
1 0 2 3
1 0 3 2
2 1 0 3
2 3 0 1
3 1 2 0
3 2 1 0
```

If perm n are all the permutations of order n , the phrase (#~ ] -:"1 /:"1) perm n is equivalent to sup n , but requires space (and time) exponential in the size of the desired result.

```   perm=: i.@! A. i.
f=: (#~ ] -:"1 /:"1) @ perm

(f -: sup)"0 i.9
1 1 1 1 1 1 1 1 1
```

supcheck has the same argument and result as sup , but incorporates checks:

```supcheck=: 3 : 0
z=. sup y
assert. 2=#\$z
assert. y={:\$z
assert. (i.y) -:"1 /:~"1 z
assert. z -: /:~ z
assert. z -: /:"1 z
)
```

A computation for the number of self-upgrading permutations derives directly from the way they are generated:

```nsup=: 3 : 'if. 1>:y do. 1x else. (nsup y-1)+(y-1)*nsup y-2 end.' M.

nsup"0 i.10
1 1 2 4 10 26 76 232 764 2620
#@sup"0 i.10
1 1 2 4 10 26 76 232 764 2620

nsup 80
245789798368839780414239398545880224872312250090845785136562176
```