More Permutation Methods to Explore:

Many of the links provided below represent various methods for computing a complete permutation set. Unfortunately many of the algorithms presented on these sites use recursion or a variation of lexicographic sorting on the actual target data structure without the efficient use of small helping data structures. Consequently, lexicographic ordering methods lead to use of three nested loops and several possible swaps. In this respect, data dependency upon the target can be dangerous especially if several swaps are attempted on very large and complex linear objects (in reference to the actual target or the source data structures).

Permutations Defined:
Alexander Bogomolny introduces "Interactive Mathematics Miscellany and Puzzles" at http://www.cut-the-knot.com/ which provides a fundamental definition of a permutation and also provides simple online methods for counting and listing all permutations. Various ways to define a permutation are also presented. Click here for actual C++ examples using recursive and lexicographic ordering methods.

Edsger Wybe Dijkstra:
"My area of interest focuses on the streamlining of the mathematical argument so as to increase our powers of reasoning, in particular, by the use of formal techniques." ~ Edsger Wybe Dijkstra a true leader in the Computer Science field and author of the Shortest Path Algorithm. For more information regarding Dr. Dijkstra's accomplishments visit http://www.cs.utexas.edu/ at the University of Texas at Austin (explore the Math and Computer Science Departments). Investigate generating permutation sets by sorting in lexicographic (alphabetic) order, without the use of recursion.

The "Johnson-Trotter" Algorithm:
Although the QuickPerm algorithms presented on this website strictly adheres to the principle of Ockham's razor, the Johnson-Trotter algorithm is often implemented as a 'last resort' miracle method upon the target linear sequence, array, or string. The Johnson-Trotter algorithm (found at the Combinatorial Object Server's web site) recursively generates permutations by transposing adjacent elements within the actual target data structure in a cyclic fashion. Click here for an example of the Steinhaus-Johnson-Trotter algorithm written in C by Frank Ruskey (1995).

Albert Nijenhuis' and Herbert S. Wilf's Combinatorial Algorithms:
Albert Nijenhuis and Herbert S. Wilf provide one of the first FORTRAN implementations of algorithms to construct random subsets and to sequence subsets in Gray code and lexicographic order. The Nijenhuis-Wilf algorithm (found at the Combinatorial Object Server's web site) is a routine for producing the next permutation. For more information regarding A. Nijenhuis' and H. Wilf's combinatorial algorithms visit http://www.scribd.com/ and reference generating random permutations in minimum-change order. Click here for the actual FORTRAN example of the Nijenhuis-Wilf algorithm published circa 1975.

The SEPA Algorithm:
The SEPA algorithm by Jeffrey A. Johnson at the Brigham Young University-Hawaii Campus is another example of a lexicographic sorting method. The goal of the SEPA algorithm is to avoid recursion without the use of complex helping data structures. (Notice the classic use of three nested loops and the execution of one or more swaps on the actual target data structure.) Click here to explore the SEPA algorithm by Jeffrey A. Johnson or research it here on this site.

What are Gray Codes?
Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953. Gray coded permutation sequences are recursively generated in a minimum change order, wherein adjacent subsets differ by the insertion or deletion of exactly one element. Visit the Hitch Hiker's Guide to Evolutionary Computation or visit http://www.scribd.com/ for more information regarding Gray codes. Click here for examples of Gray and binary conversion routines written in C by Dan T. Abell (1993). (Also, the puzzle Spinout, manufactured by Binary Arts Corporation, can be solved using Gray codes.)

Miscellaneous Links:

Solving Traveling Salesman Problems:
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook did it again! Just when you thought it was impossible to prove their 13,509-city tour through the United States (solved in 1998), they presented another solution for a 15,112-city tour of Germany in 2001. A visual display of the Germany tour can be found at http://www.math.princeton.edu/. Review their research at Rice University or visit their home page at http://www.princeton.edu/tsp/.

West Chester University
An excellent place to study Computer Science. Visit my hometown and say hello.

The Future Computer Scientists of America:
Here one can find the students that inspire new ideas.

Finite Automata (Finite-State Machines):
While racing to school one day, I thought of a great examination problem: "Design a state diagram (or a deterministic finite automata) that accepts an odd number of 'a's and an even number of 'b's in any combination." Although later I found this exact problem and solution in my library, it proved to be a rewarding challenge for my students. Click here for the actual solution discovered in my classroom.

Cross Country Races
"The times presented here are realistic."

The CCIU Homepage
The Chester County Intermediate Unit is a regional educational service agency located in Chester County, Pennsylvania. Visit http://www.tchs.info/ for more information about the Chester County Technical College High School.

Copyright © 2024 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...