At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter

35. The Magical Matrix

. By Eugene McDonnell. First published in Vector, 20, 2, (October 2003), 122-126.

Christ! What are patterns for?

         Amy Lowell, Patterns

Books on combinatorial subjects seem to believe that results are obtained seriatim, that the problem is to find the next combination or permutation or partition. Such is the case in the book Combinatorial Algorithms [1]. It is also the way the latest chapters in Knuth’s Art of Computer Programming treat these topics [2]. Roger Hui, on the other hand, takes a more organic view, and his programs all grow an entire table from a seed. This article discusses perm , his algorithm for obtaining permutation tables, using a magical matrix. I call it that because, in studying his algorithm I stumbled hard against the critical part of his algorithm that used it, and puzzled over it for a long, long time before I could see how it worked. When I did finally understand it, all I could say was that it was magic. Here are the tables of all the permutations from one to four:

+-+---+-----+-------+
|0|0 1|0 1 2|0 1 2 3|
| |1 0|0 2 1|0 1 3 2|
| | |1 0 2|0 2 1 3|
| | |1 2 0|0 2 3 1|
| | |2 0 1|0 3 1 2|
| | |2 1 0|0 3 2 1|
| | | |1 0 2 3|
| | | |1 0 3 2|
| | | |1 2 0 3|
| | | |1 2 3 0|
| | | |1 3 0 2|
| | | |1 3 2 0|
| | | |2 0 1 3|
| | | |2 0 3 1|
| | | |2 1 0 3|
| | | |2 1 3 0|
| | | |2 3 0 1|
| | | |2 3 1 0|
| | | |3 0 1 2|
| | | 3 0 2 1|
| | | |3 1 0 2|
| | | |3 1 2 0|
| | | |3 2 0 1|
| | | |3 2 1 0|
+-+---+-----+-------+

The bold portion of the 4-table is one plus the 3-table; that of the 3-table is one plus the 2-table; and even, quite trivially, that of the 2-table is 1 plus the 1-table. Hui’s algorithm is recursive for arguments 2 or greater. For arguments 0 and 1 it simply returns ,.y$0 , which gives an empty table with shape 1 0 when y is 0, and a table of shape 1 1 , having the single value 0, when it is 1. The table of order 1 is the seed used to grow all the larger tables. If we want the table of order 4 this means that we have to go back to the seed to get the table of order 2, then the table of order 3, before we work on the one we want, of order 4.

Assuming we have the table of order 3, we can get what we need by adding 1 to it, then prefixing 0 to each row:

   ] p3=:0,.>:perm 3    NB. prefix 0 to rows after adding 1
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1

After studying the code that produced this, I was sure it was going to be worked on in such a way that three more analogous tables would be made and strung together with it to give the desired result. But as I looked more at Hui’s function I couldn’t believe what I saw: it appeared that it was going to be used as an index! What in the world was happening? The thing being indexed was table mm :

   ] mm =: \:"1=i.4
0 1 2 3
1 0 2 3
2 0 1 3
3 0 1 2

I was sure that mm should be the index and p3 the thing indexed. I tried various ways of doing this, ending with:

   qw=:mm{"2 1 p3
   $qw
6 4 4
   ;/qw
+-------+-------+-------+-------+-------+-------+
|0 1 2 3|0 1 3 2|0 2 1 3|0 2 3 1|0 3 1 2|0 3 2 1|
|1 0 2 3|1 0 3 2|2 0 1 3|2 0 3 1|3 0 1 2|3 0 2 1|
|2 0 1 3|3 0 1 2|1 0 2 3|3 0 2 1|1 0 3 2|2 0 3 1|
|3 0 1 2|2 0 1 3|3 0 2 1|1 0 2 3|2 0 3 1|1 0 3 2|
+-------+-------+-------+-------+-------+-------+

This can’t be right, because, for example, the row 1 0 2 3 appears three times. In order to show you how I was at last able to understand this strange indexing, I’ll show the proper table of order 4 with its four sections side by side:

   ;/_6]\perm 4
+-------+-------+-------+-------+
|0 1 2 3|1 0 2 3|2 0 1 3|3 0 1 2|
|0 1 3 2|1 0 3 2|2 0 3 1|3 0 2 1|
|0 2 1 3|1 2 0 3|2 1 0 3|3 1 0 2|
|0 2 3 1|1 2 3 0|2 1 3 0|3 1 2 0|
|0 3 1 2|1 3 0 2|2 3 0 1|3 2 0 1|
|0 3 2 1|1 3 2 0|2 3 1 0|3 2 1 0|
+-------+-------+-------+-------+

Studying this I at last saw the pattern that Hui was using. The actors are typecast in the first section, with 0, 1, 2 and 3 playing themselves. In the second, actors 0 and 1 change roles; in the third, the three actors 0, 1 and 2 play the roles of 1, 2 and 0; in the last all four actors are in disguise: 0 acts as 1, 1 acts as 2, 2 acts as 3, and 3 acts as 0. If you look at the first rows of each of the four sections, you’ll see that they are exactly the rows of mm , the magical matrix!

Now we have to study how the magical matrix was produced. The first part gets the cast of actors:

   i.4
0 1 2 3

Classifying this gives an identity matrix:

And last, each row is replaced by its downgrade:

   ] mm=:\:"1=i.4
0 1 2 3
1 0 2 3
2 0 1 3
3 0 1 2

Now, if we index each row of mm with all of p3 , we get an array of four 6 by 4 tables:

Last, join the tables:

  ,/p3{"2 1 mm
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

And this gives the desired result. The same process works for tables of all sizes greater than one. Here is perm in all its flabbergasting entirety:

perm=: 3 : 'if.1>:y do.,:y$0 else.,/(0,.perm&.<:y){"2 1\:"1=i.y end.'

Sometimes I feel that Hui has an advantage over the rest of us, even more than is given him by his native intelligence. Since he wrote it all, and keeps improving it, he must have an instinctive knowledge of the performance of each of its parts, and thus can (usually) write functions that are faster than those written by the rest of us. I suspect that indexing is one of the fastest ways to do selecting, and thus perm is likely to be the fastest way to build permutation tables.

References

[1] Nijenhuis, A., Wilf, H. S., Combinatorial Algorithms. Academic Press, New York, (1978)
[2] Knuth, D., (home page): http://www-cs-faculty.stanford.edu/~knuth/news.html
- Pre-Fascicle 2a: Generating all n-tuples (version of 29 Aug 2003)
- Pre-Fascicle 2b: Generating all permutations (version of 29 Aug 2003)
- Pre-Fascicle 2c: Generating all combinations (version of 29 Aug 2003)

Doc/Articles/Play202

35. The Magical Matrix

References

Navigation menu

Search