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



Sun, 12 Jun 2005 02:12:53 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. all-permutations is faster than permutation

2. A permutation on permutations

3. Generating permutations

4. Finding permutations

5. All Permutations

6. Permutation

7. Permutations

8. Linked list to Permutation vector

9. Permutations

10. Puzzler: function of permutation vector

11. Fwd: re: Puzzler: Permutations and Anagrams

12. Puzzler: Permutations and Anagrams

 

 
Powered by phpBB® Forum Software