All permutations
Author Message 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

Sun, 12 Jun 2005 02:12:53 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages