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
See also
Contributed by RogerHui. Portions of the text previously appeared as part of Some Uses of { and } by Roger Hui, APL87 Conference Proceedings, May 10-14, 1987.