Essays/Self-Upgrading Permutations

From J Wiki
Jump to: navigation, search

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