a. "The magical matrix" in step a has a simple computation:

grade down each row of the identity matrix. In J:

\:"1=i.n

b. The primitive A. in J can also be used to generate

permutations. x A. y gives the x-th anagram (permutation)

of y. For example, 5 A. i.5 is 0 1 4 3 2 and _1 A. i.5

is 4 3 2 1 0. (i.!n) A. i.n gives the table of all

permutations of i.n (in lexicographic order), and

is a function that produces all permutations of i.n .

Quote:

----- Original Message -----

Sent: Tuesday, December 24, 2002 09:55 AM

Subject: All permutations

Here is a pseudocode discussion of a variation of one of Roger Hui's

Permutation Table functions:

Algorithm M (Magical matrix method for tables of lexicographic

permutations.)

This algorithm forms P, the table of all t! permutations of the t numbers

{0,

1, . , t-1}, given t = 0.

M1. [Initialize] Set P to a table with one row and signum t columns of zero.

This allows the cases t = 0 and t = 1 to be handled with no further work,

with results respectively a 1 by 0 and a 1 by 1 matrix, and the cases t > 1

to begin without further ado.

M2. [Iterate max(0, t - 1) times]

a. Make the magical matrix a square matrix of order n, where n is one

greater

than the number of columns in the current P. Its first column is the

integers

{0, 1, . , n-1}, and the following items in row i are the same set of

integers, without i. For example, if n is 3, the magical matrix will be

0 1 2

1 0 2

2 0 1

b. Add one to P and prefix a column of zeros to it. For example, if P is the

table of order 2:

0 1

1 0

it becomes

1 2

2 1

and then

0 1 2

0 2 1

c. Use this matrix as an index on each row of the magical matrix, giving a

three-dimensional array of matrices.

0 1 2

0 2 1

1 0 2

1 2 0

2 0 1

2 1 0

d. Pile the matrices atop each other, forming a single matrix, the table of

order n:

0 1 2

0 2 1

1 0 2

1 2 0

2 0 1

2 1 0

Eugene McDonnell