Essays/Self-Upgrading Permutations
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
- 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.