All Permutations
Author Message
All Permutations

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

Mon, 13 Jun 2005 06:15:18 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages