{menu} {mirror}

Scalable Permutations: A Permutation of Agreeable Ideas (PREVIEW)

By Phillip Paul Fuchs





Picture of Author Phillip P. Fuchs

Scalable Permutations Preface:
"A Permutation of Agreeable Ideas"

Permutations are an axiom for all solvable problems that we face today and permutations are the only avenue for new discoveries. It is the seed of Artificial Intelligence to consider diverse possibilities and reserve to one with the least consequences. Without the intrinsic knowledge of a permutation, learning would not be possible. Millions of children around the world would endlessly force a square peg into a round hole not even realizing a better solution exists. To prove this fact, consider the following question presented below:
What's more important? "The permutation of agreeable ideas or the common synchronization response to a proven solution."
The statement presented above is a "Catch-22" scenario and cannot be divided. A permutation is the core of all educational processes, whereas often the beginning and ending routines surrounding a permutable core is a synchronization effect. Although synchronization is clearly not the focus of this book, it's important to mention at this juncture.

Synchronization by itself has a diverse meaning in the Computer Science field, but as presented above synchronization simply implies harmonic agreement of a presented solution or an understanding of one's environment at a given time. By definition two or more things are synchronized when they work in unison.

One case of an observable synchronization effect is when a teacher (or especially a music teacher) leads a group of students by repeated demonstrations and direct examples. At first students simply follow predictable and expected protocols, but after a short period of time (hopefully) the entire class is synchronized with the teacher. Often students will announce: "I get it now!" or "I understand what you are trying to do!" At certain level of confidence, a teacher can present a modified example or a new project for the students to solve.

Synchronization is the practice mimicking what is expected, which is very similar to playing the old game "Simon Says", until the student is comfortable incorporating optimal solutions using a permutation of agreeable ideas. At this point, the teacher and student are not synchronized. A synchronization effect returns only if the student can persuade the teacher that their newly discovered solution is infallible or the student agrees with the teacher's original solution.

Algorithms are not exempt from this important observation. Responsibility always falls upon the programmer's shoulders to challenge every known solution and ultimately offer a superior one. True programmers personally seek an absolutely optimized solution, which is the Holy Grail in the Computer Science field. For these presented reasons and many more, I wrote this book...

ENJOY Scalable Permutations {Work~In~Progress Preview}


Chapter 1: Permutation Odometers
The Base-N-Odometer Model by Phillip P. Fuchs

Are we there yet?

Travelers clearly depend upon an odometer to answer this question. By definition, odometers measure a distance traveled and can accurately predict a scheduled event or repair. In contrast, the average speed at which a distance is crossed determines an arrival time. Consider a destination 120 miles away from your current location; an automobile traveling at 30 m.p.h. will arrive at this destination in approximately 4 hours, whereas an automobile traveling at 60 m.p.h. will arrive at the same destination in approximately 2 hours. Although the automobile's speed clearly influenced the arrival time, the odometer in both scenarios registers an increase of only 120 miles.

What if the same principles are applied to a permutation? One could effortlessly answer the concerns presented above. In this case, the odometer is utilized to count generations of N elements within a complete permutation set. Arriving at a solution depends upon the initial list(s) given, the speed of the computer(s), threading, and distribution (by degree). The initial list given directly corresponds to the direction of travel AND the proximity to a solution within a prioritized list simply increases the chance to succeed early...

Often permutation odometer-style models only display a current combination order as index wheels and fail to record vital information such as a simple generation count (or distance) and the next swappable target (pair) at a glance. If a common automobile mileage odometer can accomplish this small feat, then permutation odometers are not exempt from this principle. The rules still apply here as well.

As a Computer Science student, one must ask questions such as: If a standalone permutation odometer only registers the current combination order, then is it really an odometer? Can a single odometer reading (as a linear array) exist by itself and be read by other algorithms? Are programmers allowed to create practical odometer functions such as a current generation count, set(n), reset(), rewind(n), and fast-forward(n) - solely based upon an odometer reading?

As stated before, the "Base-N-Odometer" that is promoted on this website easily addresses concerns described above and is highly predictable, whereas other odometer models are more complex, certainly have more code to support the odometer model, and are difficult to grasp by many novice computer science students (in my opinion as a Computer Science teacher).

The QuickPerm algorithm presented earlier can utilize a countdown process or it can utilize a counting process. The significant difference between a countdown QuickPerm algorithm and a counting QuickPerm algorithm is the initialization of the Base-N-Odometer (coded as the primary controller array p[N]). A countdown process will initialize the controller array to corresponding index values (a maximum digit), whereas a counting process will initialize all values in the controller array to zero. Whether a countdown process or a counting process is utilized is rather debatable. Both counting processes offer similar advantages and only a few minor disadvantages if any.

In any case scenario, the primary controller array p[N] within the QuickPerm algorithm(s) is analogous to an incremental Base-N-Odometer, where the least significant digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Considering a counting QuickPerm algorithm, initially the default upper index variable i is set to one as a reference to the binary odometer digit which later advances by one each time a corresponding digit flips or rolls over. Since the upper index variable is clearly odd, the default lower index variable j is assigned to the odometer digit referenced by the upper index which coincides to the value stored in p[i] or zero. The first SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances...

Before another swap can take place, upper and lower index values must be recalculated based upon values stored in the base N odometer p[N]. Again the upper index begins at binary digit p[1] and attempts to flip each consecutive digit by adding one. The upper index will settle upon the first digit that will not flip. If the upper index is even, the lower index is assigned to the least significant odometer digit which coincides to the value stored in p[0] (or simply the lower index will remain at zero). Otherwise the lower index will be assigned to the actual odometer digit now referenced by the upper index. A second SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances.

This process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question.

Presented below is a table that compares common odometer characteristics with various computerized odometer models such as my "Base-N-Odometer", a standard automobile trip odometer, and an odometer-style generator commonly referenced by modern lexicographical (alpha-permutation) algorithms. Each odometer characteristic can have a "Yes" or "No" answer or ??? for an unknown. The third and fourth columns are open for your interpretation. Please provide a sound explanation and corresponding code to support your answer(s). I'll collect the data and compile the results within the table below:

Common Odometer Characteristics: Standalone Odometer Models
Base N ~ Mileage ~ Lexicog
Represents Current Combination Yes Yes Yes
Counts All Generations ("Distance") Yes Yes No
Sequentially Linked Digits or Wheels Yes Yes No
Expected Duplicate Digits Yes Yes No
Standalone and Shareable Readings Yes Yes ???
Defines Upper and Lower Indices at a Glance Yes ??? ???
Able to Set(n) & Distribute Readings Yes ??? ???
Able to Reset() Yes Yes ???
Able to Quickly Rewind(n) Yes ??? ???
Able to Fast-Forward(n) Yes ??? ???
Calculate the Nth Combination Yes ??? ???
Miscellaneous / Other ??? ??? ???

For more information on the Base-N-Odometer research the countdown QuickPerm algorithm followed by the counting QuickPerm algorithm.

Glossary:   {Compare and contrast the following vocabulary terms as presented below.}


Base-N-Odometer noun
  1. a core algorithm primarily used to count all generations within a permutation set containing N elements or used as a Big Integer Calculator.
  2. an algorithm for recording numerous events over time by counting in a sequentially based numbering system.
  3. an algorithm for counting events within a fixed time period that can be initialized, reset, rewound, or advanced.
  4. an algorithm for sequentially counting events exceptionally characterized by occurrences of duplicate digits and digit roll-overs.
  5. an algorithm used to identify valid target elements within a parallel linear list(s) or used to determine a pending event.

Odometer noun
  1. an instrument used to measure distance traveled.
  2. an instrument for recording an overall distance traveled counting in a universal base 10 numbering system.
  3. an instrument for measuring a distance traveled between two geographic coordinates. Often referenced as a trip-odometer.
  4. an instrument for measuring distance traveled by a sequential count characterized by occurrences of duplicate digits and digit roll-overs.
  5. an instrument used to determine a scheduled event or repair.

Permutation Odometer noun
  1. an algorithm used to count all generations within a permutation set containing N elements. Also called the "Base-N-Odometer".
  2. an algorithm for recording unique generations processed by counting in a sequentially based numbering system.
  3. an algorithm for counting generations over a fixed time period within a permutation set that can be initialized, reset, rewound, or advanced.
  4. an algorithm for sequentially counting generations exceptionally characterized by occurrences of duplicate digits and digit roll-overs.
  5. an algorithm used to identify valid target elements to swap within a linear list(s) or used to predict an imminent generation order.


Chapter 2: Countable Permutations
Historic Permutation Algorithms

What if the rules did not apply? Where would you even begin? Throughout history, mankind attempted to answer these questions with some success. Our history is more than a sequence of random mishaps, it's truly a linear progression built upon agreeable ideas and known rules. Changing the order of this linear progression could have some profound implications.

History is clearly not in an optimized order and cannot be changed. Imagine if Leonardo da Vinci invented and perfected an "aerial screw" (or helicopter) more than 250 years before the invention of a French military automobile, or even if Henry Ford successfully concealed and patented his assembly line ideas. Today our world would certainly be a different place. The permutation of a timeline is often portrayed in movies like Back to the Future and StarTrek as well.

Tracing the origin of a permutational algorithm stems from universal evolution on a grand scale, not from mankind's obsessive desire to build a better mousetrap. Adaptation is simply the modern result of an enduring permutation effort. Would dinosaurs still roam the earth if a large meteor struck our moon instead of the Earth more than 65 million years ago? Could mankind survive a catastrophic meteor strike? Without the intrinsic knowledge of a permutation, could a colony of army ants still build a bridge from other materials?

A series of linear events clearly shaped our world and this universe. As a result, imprinted upon every living organism is the will to survive. The birth of homo-sapiens clearly owes its existence to an awareness of permutations. Advances in technology throughout history can be classified into two groups: A new discovery or the improvement of an old idea. For example, the invention of a television had a profound impact on our society, but only recently LCD technology created a portable environment...

For any given unique list order, there are exactly (N! - 1) possible endings ~ ALWAYS! Therefore, incrementing the Base-N-Odometer by one produces an ending for a known permutation set. Incrementing the Base-N-Odometer by one again produces an ending for another known permutation set; and so on until the current permutation set is exhausted...

Each Base-N-Odometer reading directly maps to a unique ordered list (programmer defined by the initial list given). Therefore the upper and lower indices, defined in all permutation algorithms, depend upon various methods for incrementing and reading the odometer without producing a duplicate list. Commonly, established index variables are simply adjusted (depending upon the current Base-N-Odometer reading) to produce a desired generation sequence. Fundamentally any generation sequence is possible utilizing the Base-N-Odometer model, but often there are trade-offs. In some cases randomness is achieved by incrementing the odometer by a number greater than one, however combinations are not concentrated within the linear target data structures (a stated guideline in chapter 3). In a reversal scheme parity conditions are eliminated, but several swap calls are executed on the target data structure when the upper index exceeds a value of two (another stated guideline is compromised). Generally after progressive research utilizing various forms of the QuickPerm algorithm, the aforementioned compromises unlock numerous innovative generation sequences...





Chapter 3: Scalable Permutations!
"The Five Guiding Principles"

Recently, I received many questions regarding exhaustive combinations using linear data structures such as arrays or character strings. In particular questions like:

"Does an algorithm exist that only uses iteration (loops) to compute all possible combinations of N distinct items?" (Such that no recursion is used.)

"How do I produce all possible combinations of a character string without repeating a sequence?"

"Is there a function or class that returns just two index values (j, i) such that SWAP(a[j], a[i]) always produces a unique combination within an array a[]?" ~ Dr. Elaine R. Milito
(For the Solution Review the Meta-Permutation Class)

"Does a quick, simple, and very efficient permutation algorithm exist that exhausts all possible paths in the Traveling Salesman Problem (TSP) for any linear data structure?"

"Is there a permutation algorithm (a computer program) that completely avoids sorting and does not examine my target array?"

"If I forgot my password, can I write a computer program to decode it?"
(Note: All passwords are countable utilizing the entire character set. A much smaller subset is a countable permutation utilizing the Base-N-Odometer model.)


All of the questions presented above have one core solution: Define a procedure for generating all possible ways of rearranging N distinct items. To answer these questions I had to dig deep into my archive bag for a personal computer project I developed in the spring of 1991. Although avoiding recursion improves speed and minimizes memory usage, time is still the enemy here.

My intention was to gain a familiarity of a linear array permutation without the use of recursion. In particular, several "Example" functions independently demonstrate various iterative brute-force procedures to compute all unique combinations of any linear array type or of any character string.

The overall goal is to swap only two elements in the target array such that a unique combination is produced. The five independent C++ example programs presented here are based upon the following guidelines:

No Recursion Absolutely NO recursion shall be used. It's a well-known fact that iterative algorithms (using loops) are much more efficient than recursive algorithms that do the same thing. A true recursive function is slower and will consume more system resources (especially memory) than its iterative counterpart.

Clearly all recursive algorithms have manageable iterative algorithm counterparts, but to confidently imply the opposite that all efficient iterative algorithms have recursive algorithm counterparts is undoubtedly a false statement. In this regard, the vast universe of diverse iterative algorithms will always envelop and completely overwhelm the infinitesimal recursive algorithm universe. (Recursive algorithms are only small seeds from which certain iterative algorithms stem: Try converting MetaPerm to a truly equivalent recursive algorithm without loosing the original intent.)
No Peeking The linear permutable target can NOT be examined. Unlike lexicographic (alphabetic) ordering algorithms and iterative heuristic solution techniques which suffer from data dependency; the applications presented here use a single nested loop to create only two indexes (j, i) without scanning the target array or the target character string. To insure a unique combination, a swap(a[j], a[i]) is performed on the target before retrieving the next two new index values. The process completes when an index value exceeds a boundary of the target object list.
No Duplicates Each combination produced will not be repeated. Consecutive swaps on the target array will insure a unique permutation set (where one swap produces a new ordered list). Review the QuickPerm Reversal Algorithm to omit palindromes found within the linear permutable target. For every beginning, there are exactly (N! - 1) unique possible endings...
No Cycling Permutable subsets are concentrated within the array. Index values will not advance until all combinations are exhausted inside of the established range. After all unique combinations are exhausted, the upper index value is moved to the next level and the process repeats itself. All Examples presented here are concerned with the head or the tail of the target array. In this manner, concentrating exchanges within a prioritized list initially avoids irrational combinations and therefore prematurely solves NP-Complete problems incrementally (Promotes Scalable Permutation Solutions). In addition, solving problems incrementally clearly supports object threading in DNA genetic reconstruction projects based upon several known prime markers; this method is comparable to a polymerase chain reaction (or PCR) in small DNA samples...
No Infinite Numbers Minimize counting and storage requirements. Yes, even today all computers still have limits and computing small factorial numbers will easily exceed them. (FACT: A common 32-bit integer cannot store 13 factorial!) Therefore, counting and memory requirements are less than or equal to the integer length of the target data structure (or the target array). Although every generation sequence is countable utilizing the Base-N-Odometer AND although all of the Examples provided here will handle very large arrays, you may not have the time to wait...

NO VARIABLE DATA STACKS ALLOWED!

~ A Pseudo-Code Representation (Countdown) ~
   The Countdown QuickPerm Algorithm:

   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N+1 to control the iteration     
   initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N] to N
   initialize index variable i to 1
   while (i < N) do {
      decrement p[i] by 1
      if i is odd, then let j = p[i] otherwise let j = 0
      swap(a[j], a[i])
      let i = 1
      while (p[i] is equal to 0) do {
         let p[i] = i
         increment i by 1
      } // end while (p[i] is equal to 0)
   } // end while (i < N)



Permutation Clock


~ Comparable Pseudo-Code Representation (Counting) ~
   The Counting QuickPerm Algorithm:

   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N to control the iteration       
   initialize p[0] to 0, p[1] to 0, p[2] to 0, ..., and p[N-1] to 0
   initialize index variable i to 1
   while (i < N) do {
      if (p[i] < i) then {
         if i is odd, then let j = p[i] otherwise let j = 0
         swap(a[j], a[i])
         increment p[i] by 1
         let i = 1 (reset i to 1)
      } // end if
      else { // (p[i] equals i)
         let p[i] = 0 (reset p[i] to 0)
         increment i by 1
      } // end else (p[i] equals i)
   } // end while (i < N)







Comparable Pseudo-Code Representations


~ Pseudo-Code Representation # 1 ~
   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N+1 to control the iteration     

   initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N] to N
   initialize index variable i to 1
   while (i < N) do {
      decrement p[i] by 1
      let j = 0
      if i is odd, then let j = p[i]
      swap(a[j], a[i])
      let i = 1
      while (p[i] is equal to 0) do {
         let p[i] = i
         increment i by 1
      } // end while (p[i] is equal to 0)
   } // end while (i < N)


~ Pseudo-Code Representation # 2 ~
   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N to control the iteration       
   initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N-1] to N-1
   initialize index variable i to 1
   while (i < N) do {
      if (p[i] is greater than 0) then {
         decrement p[i] by 1
         let j = 0
         if i is odd, then let j = p[i]
         swap(a[j], a[i])
         let i = 1
      } // end if
      else { // (p[i] equals 0)
         let p[i] = i
         increment i by 1
      } // end else (p[i] equals 0)
   } // end while (i < N)


~ Pseudo-Code Representation # 3 ~
   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N+1 to control the iteration     
   initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N] to N
   initialize index variable i to 1
   while (i < N) do {
      decrement p[i] by 1
      let j = (i mod 2) * p[i]
      swap(a[j], a[i])

      let i = 1
      while (p[i] is equal to 0) do {
         let p[i] = i
         increment i by 1
      } // end while (p[i] is equal to 0)
   } // end while (i < N)

Before researching the actual C++ QuickPerm algorithms, study the "Base-N-Odometer" next.


Chapter 4: The QuickPerm Algorithms

The Countdown QuickPerm Algorithm (Head):
(Formally Example_01)

A complete permutation over a very large array is time consuming to say the least. Without a strategic plan, a permutation effort will be fruitless. In the algorithm presented below, exchanges are concentrated within the head of the target array such that one swap produces a new ordered list. Index values will not advance until all combinations are exhausted inside of the established range. Specifically, repeated access to an established upper index peak must be counted. Only when this count equals the value of the upper index in question can the upper index value proceed to the next available index level.

Consider the following example regarding a prioritized list. Imagine that your house keys were lost while surfing the net at a friend's house. Where would you begin your search? Would your search begin                             

a.) near the computer?
b.) from an adjacent room?
c.) at your house?
d.) at a neighbor’s house?

Odds are you would retrace your steps by first searching your pockets and the surrounding area repeatedly long before you would even search the neighbor’s house. Here choice "a" is intentionally placed first immediately followed by an ordered list of less likely choices (by degree). Choices very similar to these can be initially prioritized within an array before a permutation is even attempted. Frequently permutations begin with a known solution and attempt to improve upon agreeable ideas as permutable subsets. Simply stated, time management is vital when dealing with very large arrays or large character strings.

Furthermore, assume that a fast computer can complete a permutation set using a 50-element target array in exactly 10 seconds. It's also reasonable to assume this computer can complete a permutation set using a larger target array within a greater time period. Using the presented scenario above and the known factorial properties of a permutation, the following conclusions can be established:

A permutation over a new 51-element array would complete in approximately:

10 Seconds * 51 = 510 Seconds or 8.5 Minutes

A permutation over a new 52-element array would complete in approximately:

10 Seconds * 51 * 52 = 26520 Seconds or 442 Minutes or 7.37 Hours
OR 8.5 Minutes * 52 = 442 Minutes or 7.37 Hours

A permutation over a new 53-element array would complete in approximately:

10 Seconds * 51 * 52 * 53 = 1405560 Seconds or 16.27 Days

A permutation over a new 54-element array would complete in approximately:

10 Seconds * 51 * 52 * 53 * 54 = 75900240 Seconds or 2.41 Years

A permutation over a new 55-element array would complete in approximately:

10 Seconds * 51 * 52 * 53 * 54 * 55 = 4174513200 Seconds or 132.37 Years

In the above scenario, an absolute solution can probably be identified within a 53-element array. Using an array with more than 53-elements would cause an unreasonable and predictable wait. The QuickPerm algorithm presented below uses permutation subsets on the head of the target array. Often the target array a[N] is simply used to index large complex data structures. Here's the actual QuickPerm C++ algorithm for your review:
QuickPerm - Head Permutations Using a Linear Array Without Recursion
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

void QuickPerm(void)
{
   unsigned int a[N], p[N+1];
   register unsigned int i, j, tmp; // Upper Index i; Lower Index j

   for(i = 0; i < N; i++)   // initialize arrays; a[N] can be any type
   {
      a[i] = i + 1;   // a[i] value is not revealed and can be arbitrary
      p[i] = i;
   }
   p[N] = N; // p[N] > 0 controls iteration and the index boundary for i
   //display(a, 0, 0);   // remove comment to display array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
   while(i < N)
   {
      p[i]--;             // decrease index "weight" for i by one
      j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
      tmp = a[j];         // swap(a[j], a[i])
      a[j] = a[i];
      a[i] = tmp;
      //display(a, j, i); // remove comment to display target array a[]
      i = 1;              // reset index i to 1 (assumed)
      while (!p[i])       // while (p[i] == 0)
      {
         p[i] = i;        // reset p[i] zero value
         i++;             // set new index value for i (increase by one)
      } // while(!p[i])
   } // while(i < N)
} // QuickPerm()
QuickPerm - Function to Display Permutations (Optional)
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

void display(unsigned int *a, unsigned int j, unsigned int i)            
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("   swapped(%d, %d)\n", j, i);
   getch();  // press any key to continue...
} // display()


The primary index controller array in the QuickPerm algorithm above is p[N], which controls iteration and the upper index boundary for variable i. This array is initialized to corresponding index values so that a simple countdown process can be utilized. The controller array is analogous to an incremental base N odometer, where the least significant digit p[0] is always zero, digit (or wheel) p[1] counts in base 2 or binary, digit p[2] counts in base 3, ..., and digit p[N] counts in base N+1. Initial values are assigned as follows:

p[0] = 0
p[1] = 1
p[2] = 2
...
p[N] = N


Initially the default upper index variable i is set to one as a reference to the binary odometer digit which in-turn is immediately reduced by one (a countdown process). Since the upper index variable is clearly odd, the default lower index variable j is assigned to the odometer digit referenced by the upper index which coincides to the value now stored in p[i] or zero. Both index variables are properly set and the first SWAP is called...

Before another swap can take place, upper and lower index values must be recalculated based upon values stored in the base N odometer p[N]. Again the upper index begins at the binary digit p[1] and resets each consecutive ZERO digit to a corresponding index value (maximum digit). The upper index will settle upon the first odometer digit that is not zero then reduce the referenced digit by one (again a true countdown process). If the upper index is even, the lower index is assigned to the least significant odometer digit which coincides to the value stored in p[0] (or simply the lower index will remain at zero). Otherwise the lower index will be assigned to the actual odometer digit now referenced by the upper index. A SWAP is executed and this process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question.

Notice the lower index always follows the upper index's lead. Observable modifications compared to the counting QuickPerm algorithm include the following:
  1. Initializing all integers in the controller array to corresponding index values.
  2. Decrement p[i] by one before the conditional assignment j = p[i]
  3. While p[i] equals 0 DO reset p[i] to i then increment i by one.

Using a nested while loop instead of a conditional if-else statement (as described in the counting QuickPerm algorithm) clearly lead to the development of a Meta-permutation class. Although this conditional substitution can be made regardless of the counting process utilized, the Meta-permutation class precludes such a substitution in order to return valid indices.


Fundamental Analysis of QuickPerm Above {Switch to Characters}
Number of Objects
to Permute (N)
a[N] Display of
Initial Sequence
a[N] Display of
Final Sequence
Total Number of Unique
Combinations Produced (N!)
3   (Client/HTML) 1 2 3 3 2 1                      {Output} 2 * 3 = 6
4   (Client/HTML) 1 2 3 4 4 1 2 3                   {Output} 6 * 4 = 24
5   (Server/PHP) 1 2 3 4 5 5 2 3 4 1                {Output} 24 * 5 = 120
6   (Server/PHP) 1 2 3 4 5 6 6 3 4 1 2 5             {Output} 120 * 6 = 720
7   (Server/PHP) 1 2 3 4 5 6 7 7 2 3 4 5 6 1           {Output} 720 * 7 = 5040
8   (Server/PHP) 1 2 3 4 5 6 7 8 8 3 4 5 6 1 2 7        {Output} 5040 * 8 = 40320
9   (Client/JavaScript) 1 2 3 4 5 6 7 8 9 9 2 3 4 5 6 7 8 1     {Output} 40320 * 9 = 362880
if N is even 1 2 3 . . . (N - 1) N N 3 4 . . . (N - 2) 1 2 (N - 1) (N - 1)! * N = N!
if N is odd 1 2 3 . . . (N - 1) N N 2 3 . . . (N - 1) 1 (N - 1)! * N = N!


 A Permutation Ruler:
A Permutation Ruler

The graph below reflects how the value stored in the lower index variable j consistently reduces by one when the upper index variable i is odd, otherwise j is assigned a zero value. For each reference to j when i is odd, the lower index variable j will be assigned to the upper index variable “i – 1” then “i – 2” until the lower index variable j reaches zero. To control this iteration behavior, the value stored in the controller array p[i] is initialized to the same value stored in the upper index variable i (as mentioned above) then repeatedly reduced by one and assigned to the lower index variable j. This process continues until the lower index variable j reaches 0 then repeats. (Please note, the lower index variable j can also begin at zero and advance by one until the upper index value is reached.) This behavior is strictly controlled by the following statement:

IF i is odd then j = p[i] otherwise j = 0

Which in-turn translates to the following C++ statement:

j = i % 2 * p[i];


Tracking the Lower Index
(Click here to enlarge graph.)


Next compare this algorithm to the counting QuickPerm algorithm.



The Counting QuickPerm Algorithm (Head):
A Comparable Solution Inspired by Heap's Algorithm

The QuickPerm algorithm presented earlier utilized a countdown process, whereas this algorithm (below) will utilize a counting process. The significant difference between a countdown QuickPerm algorithm and a counting QuickPerm algorithm is the initialization of the primary controller array p[N]. A countdown process will initialize the controller array to corresponding index values, whereas a counting process will initialize all values in the controller array to zero. Whether a countdown process or a counting process is utilized is rather debatable. Both counting processes offer similar advantages and only a few minor disadvantages if any.

In any case scenario, the primary controller array p[N] within the QuickPerm algorithm(s) is analogous to an incremental base N odometer, where the least significant digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Initially the default upper index variable i is set to one as reference to the binary odometer digit which later advances by one each time a corresponding digit flips or rolls over. Since the upper index variable is clearly odd, the default lower index variable j is assigned to the odometer digit referenced by the upper index which coincides to the value stored in p[i] or zero. The first SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances...

Before another swap can take place, upper and lower index values must be recalculated based upon values stored in the base N odometer p[N]. Again the upper index begins at binary digit p[1] and attempts to flip each consecutive digit by adding one. The upper index will settle upon the first digit that will not flip. If the upper index is even, the lower index is assigned to the least significant odometer digit which coincides to the value stored in p[0] (or simply the lower index will remain at zero). Otherwise the lower index will be assigned to the actual odometer digit now referenced by the upper index. A second SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances.

This process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question.

Observable modifications compared to the countdown QuickPerm algorithm include the following:
  1. Initializing all integers in the controller array to zero.
  2. Increment p[i] by one after the conditional assignment j = p[i]
  3. While p[i] equals i DO reset p[i] to zero then increment i by one.
Also notice the nested while loop was replaced by a conditional if-else statement, which in-turn reduced the size of the index controller array by one integer. Although performance is relatively unchanged, using a nested while loop instead of a conditional if statement clearly lead to the development of a permutation class as presented in Example_05. This conditional substitution can be made regardless of the counting process utilized. Here's the counting QuickPerm C++ algorithm for your review:

A Counting QuickPerm Algorithm - Head Permutations Using a Linear Array without Recursion

// NOTICE:  Copyright 2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

void QuickPerm(void) {
   unsigned int a[N], p[N];
   register unsigned int i, j, tmp; // Upper Index i; Lower Index j

   for(i = 0; i < N; i++) {  // initialize arrays; a[N] can be any type

      a[i] = i + 1;   // a[i] value is not revealed and can be arbitrary
      p[i] = 0;       // p[i] == i controls iteration and index boundaries for i
   }
   //display(a, 0, 0);   // remove comment to display array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)

   while(i < N) {
      if (p[i] < i) {
         j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
         tmp = a[j];         // swap(a[j], a[i])
         a[j] = a[i];
         a[i] = tmp;
         //display(a, j, i); // remove comment to display target array a[]
         p[i]++;             // increase index "weight" for i by one

         i = 1;              // reset index i to 1 (assumed)
      } else {               // otherwise p[i] == i
         p[i] = 0;           // reset p[i] to zero
         i++;                // set new index value for i (increase by one)
      } // if (p[i] < i)

   } // while(i < N)
} // QuickPerm()
QuickPerm - Function to Display Permutations (Optional)

// NOTICE:  Copyright 2010, Phillip Paul Fuchs

void display(unsigned int *a, unsigned int j, unsigned int i) {
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("   swapped(%d, %d)\n", j, i);
   //getch();  // Remove comment for "Press any key to continue" prompt.        
} // display()



Fundamental Analysis of QuickPerm Above {Switch to Characters}
Number of Objects
to Permute (N)
a[N] Display of
Initial Sequence
a[N] Display of
Final Sequence
Total Number of Unique
Combinations Produced (N!)
3 1 2 3 3 2 1 2 * 3 = 6
4 1 2 3 4 2 3 4 1 6 * 4 = 24
5 1 2 3 4 5 5 2 3 4 1 24 * 5 = 120
6 1 2 3 4 5 6 4 5 2 3 6 1 120 * 6 = 720
7 1 2 3 4 5 6 7 7 2 3 4 5 6 1 720 * 7 = 5040
8 1 2 3 4 5 6 7 8 6 7 2 3 4 5 8 1 5040 * 8 = 40320
9 1 2 3 4 5 6 7 8 9 9 2 3 4 5 6 7 8 1 40320 * 9 = 362880
if N is even 1 2 3 . . . (N - 1) N (N - 2) (N - 1) 2 3 4 . . . N 1 (N - 1)! * N = N!
if N is odd 1 2 3 . . . (N - 1) N N 2 3 . . . (N - 1) 1 (N - 1)! * N = N!


 A Permutation Ruler:
A Permutation Ruler

Next is tail combinations represented in EXAMPLE 02.


The Countdown QuickPerm Algorithm (Tail):
(Formally EXAMPLE_02)

EXAMPLE 02 - Tail Permutations Using a Linear Array Without Recursion
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

void example_02(void)
{
   const unsigned int ax = N - 1;   // constant index ceiling (a[N] length)
   unsigned int a[N], p[N+1];       // target array and index control array
   register unsigned int i, j, tmp; // index variables and tmp for swap 

   for(i = 0; i < N; i++)   // initialize arrays; a[N] can be any type

   {
      a[i] = i + 1;   // a[i] value is not revealed and can be arbitrary
      p[i] = i;
   }
   p[N] = N; // p[N] > 0 controls iteration and the index boundary for i
   //display(a, 0, 0);   // remove comment to display initial array a[]
   i = 1;   // setup first swap points to be ax-1 and ax respectively (i & j)
   while(i < N)
   {
      p[i]--;                // decrease index "weight" for i by one

      j = ax - i % 2 * p[i]; // IF i is odd then j = ax - p[i] otherwise j = ax
      i = ax - i;            // adjust i to permute tail (i < j)
      tmp = a[j];            // swap(a[i], a[j])
      a[j] = a[i];
      a[i] = tmp;

      //display(a, i, j);    // remove comment to display target array a[]
      i = 1;                 // reset index i to 1 (assumed)
      while (!p[i])          // while (p[i] == 0)
      {
         p[i] = i;           // reset p[i] zero value
         i++;                // set new index value for i (increase by one)

      } // while(!p[i])
   } // while(i < N)
} // example_02()
EXAMPLE 02a - Function to Display Permutations (Optional)
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

void display(unsigned int *a, unsigned int i, unsigned int j)                  
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("   swapped(%d, %d)\n", i, j);
   getch();  // press any key to continue...
} // display()



Fundamental Analysis of Permutation Example 02 Above
Number of Objects
to Permute (N)
a[N] Display of
Initial Sequence
a[N] Display of
Final Sequence
Total Number of Unique
Combinations Produced (N!)
3 1 2 3 3 2 1 2 * 3 = 6
4 1 2 3 4 2 3 4 1 6 * 4 = 24
5 1 2 3 4 5 5 2 3 4 1 24 * 5 = 120
6 1 2 3 4 5 6 2 5 6 3 4 1 120 * 6 = 720
7 1 2 3 4 5 6 7 7 2 3 4 5 6 1 720 * 7 = 5040
8 1 2 3 4 5 6 7 8 2 7 8 3 4 5 6 1 5040 * 8 = 40320
9 1 2 3 4 5 6 7 8 9 9 2 3 4 5 6 7 8 1 40320 * 9 = 362880
if N is even 1 2 3 . . . (N - 1) N 2 (N - 1) N 3 4 . . . (N - 2) 1 (N - 1)! * N = N!
if N is odd 1 2 3 . . . (N - 1) N N 2 3 . . . (N - 1) 1 (N - 1)! * N = N!

Next is EXAMPLE 03 which inclusively reverses elements from index j to index i. (Head Reversals)


(Countdown) QuickPerm Head Lexicography:
(Formally Example_03 ~ Palindromes)

The QuickPerm algorithm (below) unequivocally demonstrates lexicography without any inspection of the user's target array. In addition, the core of the QuickPerm algorithm is extremely versatile as well as highly predictable. Prove this statement by considering a permutation algorithm that reverses an index range from the first element in the target array to the upper index as previously defined. Notice the modified QuickPerm algorithm below does not implement an Odd or Even condition upon the upper index in order to control the behavior of the lower index. Here the lower index will always begin at zero regardless of the upper index parity, however the core Base-N-Odometer still controls the upper index. In addition, the target data element referenced by the lower index is a prime candidate for multitasking and for large event distribution (since the mid-point here is easily defined as well). To illustrate the versatility of the Base-N-Odometer (or the core), consider the following Pseudo-Code representation:


~ Countdown QuickPerm Reversals (Pseudo-Code) ~
   let a[] represent an arbitrary list of objects to permute
   let N equal the length of a[]
   create an integer array p[] of size N+1 to represent the Base-N-Odometer
   initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N] to N
   initialize index variable i to 1
   while (i < N) do {
      decrement p[i] by 1
      reverse(a[0], a[i])
      let i = 1
      while (p[i] is equal to 0) do {  // Set i Using the Base-N-Odometer
         let p[i] = i
         increment i by 1
      } // end while (p[i] is equal to 0)
   } // end while (i < N)



Recall that each Base-N-Odometer reading directly maps to a unique ordered list (programmer defined by the initial list given). Therefore the upper and lower indices depend upon various methods for incrementing and reading the odometer without producing a duplicate list. Commonly, established index variables are simply adjusted (depending upon the current Base-N-Odometer reading) to produce a desired generation sequence. Fundamentally any generation sequence is possible utilizing the Base-N-Odometer model, but often there are trade-offs. In some cases randomness is achieved by incrementing the odometer by a number greater than one, however combinations are not concentrated within the linear target data structures (a stated guideline). In the specific case below parity conditions are eliminated, but several swap calls are executed on the target data structure when the upper index exceeds a value of two (another stated guideline is compromised). Generally after progressive research utilizing various forms of the QuickPerm algorithm, the aforementioned compromises unlock numerous innovative generation sequences...

As described previously, the QuickPerm algorithm can utilize a countdown process or it can utilize a counting process. The significant difference between a countdown QuickPerm algorithm and a counting QuickPerm algorithm is the initialization of the Base N Odometer (coded as the primary controller array p[N]). A countdown process (as presented below) will initialize the controller array to corresponding index values (a maximum digit), whereas a counting process will initialize all values in the controller array to zero. Both processes will exclusively decrement or increment the Base-N-Odometer respectively to define the upper index, but now without an apparent parity restriction.



The primary index controller array in the QuickPerm algorithm below is p[N], which controls iteration and the upper index boundary for variable i. This array is initialized to corresponding index values so that a simple countdown process can be utilized. The controller array is analogous to an incremental Base-N-Odometer, where the least significant digit p[0] is always zero, digit (or wheel) p[1] counts in base 2 or binary, digit p[2] counts in base 3, ..., and digit p[N] counts in base N+1. Initial values are assigned as follows:

p[0] = 0
p[1] = 1
p[2] = 2
...
p[N] = N

Initially the default upper index variable i is set to one as a reference to the binary odometer digit p[1] which in-turn is immediately reduced by one (a countdown process). Since no parity condition exists, the default lower index variable j is assigned a zero value. Both index variables are properly set and two target elements are reversed...

Before more data elements are reversed, the upper index value must be recalculated based upon values stored in the Base-N-Odometer p[N]. Again the upper index begins at the binary digit p[1] and resets each consecutive ZERO digit to a corresponding index value (a maximum digit). The upper index will settle upon the first odometer digit that is not zero then reduce the referenced digit by one (again a true countdown process). If the previous reversal process increased the lower index value, then the lower index value must be reset to a zero value. Target data elements inclusively between the lower index and the upper index are reversed. This process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question.

The proof here is simple: Remove the parity condition placed upon the upper index and WA-LA another predictable permutation set where the end result will always be the reverse of the original target array. Here's the C++ countdown QuickPerm Head Reversal algorithm for your review: (BTW - The proof is a later exercise!)

Example_03 - Permutation Reversals on the Head of a Linear Array Without Using Recursion
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

void example_03(void)
{
   unsigned int a[N], p[N+1];       // target array and index control array 
   register unsigned int i, j, tmp; // index variables and tmp for swap 

   for(i = 0; i < N; i++)   // initialize arrays; a[N] can be any type
   {
      a[i] = i + 1;   // a[i] value is not revealed and can be arbitrary

      p[i] = i;
   }
   p[N] = N; // p[N] > 0 controls iteration and the index boundary for i
   //display(a);   // remove comment to display array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
   while(i < N)
   {
      p[i]--;             // decrease index "weight" for i by one
      j = 0;              // reset j to 0

      do                  // reverse target array from j to i
      {
         tmp = a[j];      // swap(a[i], a[j])
         a[j] = a[i];
         a[i] = tmp;
         j++;             // increment j by 1
         i--;             // decrement i by 1
      } while (j < i);

      //display(a);       // remove comment to display target array a[]
      i = 1;              // reset index i to 1 (assumed)
      while (!p[i])       // while (p[i] == 0)
      {
         p[i] = i;        // reset p[i] zero value
         i++;             // set new index value for i (increase by one)

      } // while(!p[i])
   } // while(i < N)
} // example_03()
EXAMPLE 03a - Function to Display Permutations (Optional)
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs                         

void display(unsigned int *a)
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("\n");
   getch();  // press any key to continue...
} // display()

Fundamental Analysis of Permutation Example 03 Above
Number of Objects
to Permute (N)
a[N] Display of
Initial Sequence
a[N] Display of
Final Sequence
Total Number of Unique
Combinations Produced (N!)
3 1 2 3 3 2 1 2 * 3 = 6
4 1 2 3 4 4 3 2 1 6 * 4 = 24
5 1 2 3 4 5 5 4 3 2 1 24 * 5 = 120
6 1 2 3 4 5 6 6 5 4 3 2 1 120 * 6 = 720
7 1 2 3 4 5 6 7 7 6 5 4 3 2 1 720 * 7 = 5040
8 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 5040 * 8 = 40320
9 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 40320 * 9 = 362880
N 1 2 3 . . . (N - 1) N N (N - 1) . . . 3 2 1 (N - 1)! * N = N!


Often duplicate generations within a complete permutation set are not desirable. If there are duplicate elements within a target array, there will be duplicate generations within the permutation set. The QuickPerm Reversal Algorithm presented above stemmed from an early single-pass Palindrome Detection Algorithm I developed in the year 1984. Depending upon the upper and lower indices, duplicate generations - as a fractional palindrome substring - can be detected and omitted when target elements are swapped. Consider two fundamental target strings such as "ABCDEFFEDCBA" and "ABCDEFABCDEF" to research duplicate patterns within ordered permutation sets. (Please note, the examination of target arrays violates a previously stated guideline: "The linear permutable target can NOT be examined".) Presented below is a "Permutation Ruler" which illustrates this eloquent principle:

 A Permutation Ruler: (The Origin)
A Permutation Ruler

Next is EXAMPLE 04 which inclusively reverses elements from index i to index j. (Tail Reversals)


(Countdown) QuickPerm Tail Reversals:
(Formally EXAMPLE_04)

EXAMPLE 04 - Permutation Reversals on the Tail of a Linear Array Without Using Recursion
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

void example_04(void)
{
   const unsigned int ax = N - 1;   // constant index ceiling (a[N] length)
   unsigned int a[N], p[N];         // target array and index control array 
   register unsigned int i, j, tmp; // index variables and tmp for swap 

   for(i = 0; i < N; i++)   // initialize arrays; a[N] can be any type

   {
      a[i] = N - i;   // a[i] value is arbitrary and not revealed
      p[i] = N - i;
   }
   //display(a);   // remove comment to display array a[]
   i = ax;   // setup first swap point to be ax
   while (i > 0)
   {
      p[i]--;             // decrease index "weight" for i by one

      i--;                // i must be less then j (i < j)
      j = ax;             // reset j to ax
      do                  // reverse target array from i to j
      {
         tmp = a[j];      // swap(a[i], a[j])

         a[j] = a[i];
         a[i] = tmp;
         j--;             // decrement j by 1
         i++;             // increment i by 1
      } while (j > i);
      //display(a);       // remove comment to display target array a[]
      i = ax;             // reset index i to ax (assumed)

      while (!p[i])       // while (p[i] == 0)
      {
         p[i] = N - i;    // reset p[i] zero value
         i--;             // set new index value for i (decrease by one)
      } // while (!p[i])
   } // while (i > 0)

} // example_04()
EXAMPLE 04a - Function to Display Permutations (Optional)
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs                         

void display(unsigned int *a)
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("\n");
   getch();  // press any key to continue...

} // display()


Fundamental Analysis of Permutation Example 04 Above
Number of Objects
to Permute (N)
a[N] Display of
Initial Sequence
a[N] Display of
Final Sequence
Total Number of Unique
Combinations Produced (N!)
3 3 2 1 1 2 3 2 * 3 = 6
4 4 3 2 1 1 2 3 4 6 * 4 = 24
5 5 4 3 2 1 1 2 3 4 5 24 * 5 = 120
6 6 5 4 3 2 1 1 2 3 4 5 6 120 * 6 = 720
7 7 6 5 4 3 2 1 1 2 3 4 5 6 7 720 * 7 = 5040
8 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 5040 * 8 = 40320
9 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 40320 * 9 = 362880
N N (N - 1) . . . 3 2 1 1 2 3 . . . (N - 1) N (N - 1)! * N = N!

The Meta-Permutation class supplies head and tail indices to EXAMPLE 05, which is next on our tour...


Chapter 5: The Universal Meta-Permutation Algorithm
Presented as Example_05

"Is there a function or class that returns just two index values (i, j) such that SWAP(a[i], a[j]) always produces a unique combination within an array a[]?" ~ Dr. Elaine R. Milito (previously unsolved)

Presented below is the C++ algorithm which answered Dr. Milito's question proposed sometime after the Fall of 1986. Using a target array of size N, two distinct variables (j, i) can be accessed for all head transpositions as well as two distinct variables (q, r) for all tail transpositions. Given two target arrays called h[N], t[N] and the Meta-permutation object s(N), SWAP(h[s.j], h[s.i]) is valid for all head combinations whereas SWAP(t[s.q], t[s.r]) is valid for all tail combinations provided that all SWAP calls are followed by a single s.next() call to calculate four new index values.

Using a nested while loop in the countdown QuickPerm algorithm clearly lead to the development of a Meta-permutation class (below). In contrast, replacing the nested while loop with a conditional if-else statement as described in the counting QuickPerm algorithm causes the Meta-permutation class to "skip" index calculations due to an obvious dependency on the outer loop. Although this conditional substitution can be made regardless of the counting process utilized, the Meta-Permutation Class precludes such a substitution in order to return valid indices.

Example_05 efficiently combines the four previous examples by utilizing a single Meta-Permutation Class aptly named MetaPerm. Here's the Meta-Permutation Class written in C++ for your review:


MetaPerm Class - Combining the Four Previous Examples

// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs

#define N    12   // number of elements to permute.  Let N > 2

class MetaPerm {
   private:
      unsigned int *p, ax;       // index control pointer and index ceiling indicator

   public:
      unsigned int i, j, q, r;   // declare indexes for head and tail permutations

      void next(void);           // calculate new indexes for head and tail permutations

      MetaPerm(unsigned int n);  // initialize first set of indices (i, j, q, & r)

      ~MetaPerm(void) { delete [] p; };
};


MetaPerm::MetaPerm(unsigned int n)
{
   p = new unsigned int[n+1];    // declare primary index controller array
   for(i = 0; i <= n; i++)       // initialize primary index controller array
      p[i] = i;

   i = 1;                        // initialize head indices i & j
   j = 0;
   ax = n - 1;                   // define index ceiling
   q = ax - i;                   // initialize tail indices q & r
   r = ax - j;
   p[1] = 0;                     // Record initialization event of indices above
} // MetaPerm(unsigned int) Constructor (Initialize or Reset Permutation)


void MetaPerm::next(void)
{
   i = 1;                       // reset index i to 1 (assumed)
   while (!p[i])                // while (p[i] == 0)
   {
      p[i] = i;                 // reset p[i] zero value
      i++;                      // set new index value for i (increase by one)
   }
   p[i]--;                      // decrease index "weight" for i by one
   j = i % 2 * p[i];            // IF i is odd then j = p[i] otherwise j = 0
   q = ax - i;                  // adjust tail indices q and r such that q < r
   r = ax - j;
}  // MetaPerm::next()
/*******************************************************************************************/ /*******************************************************************************************/
void example_05(void)
// Combines the four previous examples using one MetaPerm class. { MetaPerm s(N); unsigned int ex1[N], ex2[N], ex3[N], ex4[N]; register unsigned int tmp; for(unsigned int i = 0; i < N; i++) // initialize arrays for permutations { ex1[i] = i + 1; ex2[i] = ex1[i]; ex3[i] = ex1[i]; ex4[i] = N - i; } //display(ex1); // remove comment to display head permutations //display(ex2); // remove comment to display tail permutations //display(ex3); // remove comment to display permutations using head reversals //display(ex4); // remove comment to display permutations using tail reversals while (s.i < N) { tmp = ex1[s.j]; // swap(ex1[s.i], ex1[s.j]) ex1[s.j] = ex1[s.i]; ex1[s.i] = tmp; //display(ex1); // remove comment to display head permutations tmp = ex2[s.r]; // swap(ex2[s.q], ex2[s.r]) ex2[s.r] = ex2[s.q]; ex2[s.q] = tmp; //display(ex2); // remove comment to display tail permutations s.j = 0; // establish lower range for head reversals s.r = N - 1; // establish upper range for tail reversals do // demonstration of permutations using reversals { tmp = ex3[s.j]; // reversal of array head from s.j to s.i ex3[s.j] = ex3[s.i]; ex3[s.i] = tmp; s.j++; s.i--; tmp = ex4[s.r]; // reversal of array tail from s.q to s.r ex4[s.r] = ex4[s.q]; ex4[s.q] = tmp; s.r--; s.q++; } while (s.j < s.i); // or while(s.q < s.r); //display(ex3); // remove comment to display permutations using head reversals //display(ex4); // remove comment to display permutations using tail reversals s.next(); // create new index values for another unique exchange } // while (s.i < N) } // example_05()


MetaPerm Function to Display Permutations (Optional)

// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs                                          

void display(unsigned int *a)
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("\n");
   // getch();  // Remove comment for "Press any key to continue"
} // display()

Now try downloading the five C++ examples and solving the permutation exercises.




Permutation Clock



Chapter 6: Solving the Unsolvable

{Work~In~Progress}


Chapter 7: Problem Distribution

{Work~In~Progress}


Chapter 8: The Permutation Clock
By Phillip Paul Fuchs

Perpetual Improvements: Everyday programmers are challenged to create very efficient algorithms that follow a concise mathematical model. The end-result is often a well-planned computer application focused upon a specific solution. Application upgrades often stem from user demands directly fed-back to the programmers. In this respect, idle time within any application is virtually left unchallenged by most programmers.

The difficult problems that we face today can not be left unchallenged by static applications.

The Permutation Clock illustrated below automates perpetual improvements during idle periods within any computer application. By extracting a concise linear solution from the application, a new combination can be created then inspected. Upon rejection another combination is created, otherwise the new order (or new combination) is integrated into the current application and the process is repeated. Presented below are two Permutation Clock Models for your review:

Permutation Clock 1


Permutation Clock 2


Chapter 9: Iteration ~ VS ~ Recursion

{Work~In~Progress}


Chapter 10: Analysis of the QuickPerm and MetaPerm Algorithms

{Work~In~Progress}


Chapter 11: Permutation Exercises

The exercises presented below relate to the five Example functions found on this web site. The word Example shall be taken in this context. For every problem listed below, there is a known solution. Solutions from one exercise problem are independent and usually do not carry into other problems. Your solution(s) can be evaluated by emailing phillip.fuchs@gmail.com {click here}. All serious attempts will receive a reply and solution (NO homework projects). Please consider giving a tax-deductible donation.
  1. For every odd reference call, index values of a 0 and a 1 are produced. Improve the performance of QuickPerm (EXAMPLE_01) by alternating between two functions. Calling one function will simply return a 0 and a 1, whereas calling the second function will calculate new index values. (Your output will remain the same as the original.)


  2. QuickPerm (EXAMPLE_01) computes the index value of j using the following line:
    j = i % 2 * p[i];
    Rewrite this line to improve performance. Time each improvement and present your findings in a table format. (HINT: Addition is much faster than multiplication.)

    For extra credit, remove the nested while loop and compute the second index value i. Try replacing the nested loop with a fractal equation that depends upon the established range and the first index value generated. (A very large integer or binary operations will also work in this case.)


  3. Rewrite EXAMPLE_02 using recursion and compare it to the efficiency of using iteration. Although recursion and iteration are theoretically equivalent, converting an iterative algorithm to a recursive one is difficult and sometimes impossible. Begin by using a known recursive algorithm and attempt to modify it.


  4. Did you actually purchase a computer that was three times the speed of your old computer? Is Moore's Law accurate or is Dr. Gordon E. Moore just a wise salesman? Here's your chance to prove it before buying your next computer!

    Write an algorithm to accurately time each Example for five different lengths of permutation sets. Be consistent for each Example and do not use a time less than a second more than once. (If you gather times for N as 10, 11, 12, 13, and 14 for QuickPerm (formally EXAMPLE_01), you must use the same values for the remaining four Examples.) Also, predict the amount of time it would take to permute 50, 75, and 100 items. Present your findings in a table format and save them. Repeat this process using a different CPU speed and compare your findings. (Include an accurate description of the advertised speed of each computer that you used for this exercise.)


  5. Describe possible improvements for each Example presented. Include in your essay descriptions on divide & conquer, dynamic programming, distributed processing, and time management procedures.


  6. Using EXAMPLE_03 and EXAMPLE_04, rewrite and reintegrate the display() function such that an actual reversed range is displayed after the permutation set. Follow QuickPerm (formally EXAMPLE_01) and EXAMPLE_02 display() function, but instead of showing the two indexes that were SWAPPED; simply present the two index values as a range that were REVERSED. (For clarity, change the display() function for all five Examples to output proper set notation.)


  7. The concept of a permutation ruler as described in the QuickPerm algorithm combined with Example_02's tail combinations is comparable to a "zipper". Write a new application that combines the QuickPerm algorithm head permutation set with Example_02 tail permutation set. Recall that only when the upper index is odd, a counting process causes the lower index variable to begin at zero then advance by one; whereas a countdown process causes the lower index variable to begin at one less than the current upper index then reduce by one. Four (4) distinct permutation sets (with obvious duplications) are produced by utilizing a combination of both counting and countdown processes. Using a single target a[], measure statistical significance (describe the duplicate items produced) and when to halt execution. How would your argument change by using two or more duplicate targets initially?

    In addition, implement mutually exclusive head and tail combinations upon each half of the target array. Be creative here. Again accurately measure statistical significance, but in this case there will be four (4) distinct sets produced for each head-head scenario and four (4) distinct sets produced for each tail-tail scenario. For extra credit, consider dividing the target array in half by using a tail-head scenario where the midpoint is shared respectively. Present ALL your findings in a formal report.

    Repeat this exercise combining EXAMPLE_03 head reversals with EXAMPLE_04 tail reversals. Is the counting process relevant? Why or why not? (Overall Hint: Be creative, there are more countable sets to consider especially when over-indexing an array...)


  8. Following EXAMPLE_04, rewrite EXAMPLE_02 and MetaPerm (EXAMPLE_05) such that index values are not simply adjusted. (In EXAMPLE_02, the length of the index control array p[] must equal N and not N+1.)


  9. Notice the p[N] controller array's behavior is analogous to an incremental Base-N-Odometer, where the least significant digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Utilizing this model, upper and lower indices can easily map to any valid Base-N-Odometer setting. To illustrate this principle, consider the following (counting) Base-N-Odometer reading:
    
        10!     9!    8!    7!    6!    5!    4!    3!    2!    1!    0!  <- Factorial Base
    3628800 362880 40320  5040   720   120    24    06    02    01    01  <- Positional Value
      p[10]  p[09] p[08] p[07] p[06] p[05] p[04] p[03] p[02] p[01] p[00]  <- Base-N-Odometer Array
    --------------------------------------------------------------------
       {01}   {00}  {00}  {07}  {03}  {02}  {04}  {00}  {01}  {01}  {00}  <- Base-N-Odometer Reading
    
    
    Solely based upon the odometer reading above, exactly 3,666,579 swap() calls were performed on the target data structure(s). The upper index returned an odd value 1 and the lower index returned 0 (or the current value stored in p[1]), after-which a swap was called and p[1] advanced by one. Before the next swap call, the upper index pointer will flip the odd p[1] digit then settle upon the even p[2] digit and as a result the lower index will be assigned to the value stored in p[0] (or zero). Eventually a swap(0, 2) is called then p[2] advances by one...

    The above swap() call calculation (3,666,579) is similar to converting any base number to another base, such as a binary to decimal base conversion. Reading the Base-N-Odometer (above) from left to right, a current generation count (excluding the original) is calculated as follows:
    
    (1 * 10!) + (7 * 7!) + (3 * 6!) + (2 * 5!) + (4 * 4!) + (1 * 2!) + (1 * 1!)
    

    Given the following six incremental base 10 odometer readings for a counting QuickPerm algorithm, calculate the current generation count, determine the upper and lower index values then compute the next odometer setting after a SWAP() is called:
    
    -------------------------------------------------
    p[9] p[8] p[7] p[6] p[5] p[4] p[3] p[2] p[1] p[0]
    -------------------------------------------------
    
    {00} {04} {04} {06} {01} {00} {02} {02} {01} {00}
    
    {09} {00} {01} {03} {00} {01} {03} {02} {01} {00}
    
    {00} {00} {00} {00} {00} {00} {00} {00} {00} {00}
    
    {08} {08} {07} {06} {05} {04} {03} {02} {01} {00}
    
    {09} {08} {07} {06} {05} {04} {03} {02} {01} {00}
    
    {09} {08} {05} {03} {02} {04} {03} {02} {01} {00}
    

    Repeat this exercise using the countdown QuickPerm algorithm then advance the fifth odometer reading (above) for thirty SWAP() call iterations.

    Also using both counting methods, accurately describe the Base-N-Odometer reading at the beginning, at the mid-point *~KEY~*, at the end, and at the exact reverse order. (Hint: Review the fundamental analysis of the QuickPerm algorithms when permutable subset lengths are even and odd.)


  10. Modify the MetaPerm object (EXAMPLE_05) for distributed processing.


  11. Discuss the impact of converting the MetaPerm class to a hardware solution.


  12. Sometimes optimizing the compiler and disabling the video output will increase performance. Implement and document five optimizations that significantly improve performance for all the Examples presented. Follow the guidelines presented at Programming Optimization by Paul Hsieh.


  13. Rewrite QuickPerm (EXAMPLE_01) and MetaPerm (EXAMPLE_05) in a programming language(s) of your choice. Compare the efficiency of the Class object presented in MetaPerm with the QuickPerm algorithm as written. Before rewriting and timing these algorithms, modify MetaPerm (without removing the Class) to produce the exact results as QuickPerm. Present your findings in a formal report.


  14. Provide a formal algorithm analysis for both QuickPerm algorithms. For this exercise, calculate the approximate running time of QuickPerm in Big-O notation O(), including a strict/tight calculation of Θ() Theta and the lower bound Ω() Omega. (This exercise will also help you answer the extra credit presented in exercise #2.)


  15. Generating and storing indices without swapping elements in the target array significantly improves performance. Unfortunately, to store individual index sets as two integers would consume a vast amount of memory. Therefore, a binary storage method must be considered and carefully developed. By using simple binary operators, one can create a binary stack (FIFO) directly related to index counters. For example, '10110101101' represents the first 5 index values for i found in QuickPerm (formally EXAMPLE_01). To minimize memory requirements, utilize repeating patterns and consider several segmented binary stacks for each index. Ending i's binary segment depends upon if j is greater than 0 (as seen above). Binary stack operations and segments are transparent to the overall process.

    Rewrite QuickPerm (EXAMPLE_01) and implement a binary storage method for both indices. Provide a fundamental analysis for all storage requirements. (Try describing a relationship between each binary number segment and prime numbers.)


  16. Encryption algorithms depend upon password(s) to scramble data files. Advanced encryption algorithms avoid repeating patterns within the data file by applying various methods to extend the length of a user's password (unique like pi). Write an algorithm to encrypt or decrypt a file by permuting the user's password. Also, consider incorporating binary operations (an exclusive OR), password rotation, and Cyclic Redundancy Check (CRC) numbers.

    For instance, assume you are modifying QuickPerm and the user's password is stored in the character string a[]. Consider expanding upon the following C++ statements to encode a data character from a file's IO stream:
    ...
    swap(a[j], a[i]);
    read(data_ch);
    new_ch = a[j] ^ CRC(a) ^ data_ch;
    save(new_ch);
    ...


  17. Using all 26 lowercase letters in the alphabet, write a program to produce all five letter words. Also, highlight all valid words that are prime. Study the Countdown QuickPerm Reversal Algorithm (Example_03) to produce combinations of 5 letter groups from 26 letters.


  18. Solve the traveling salesman problem (TSP) using the QuickPerm algorithms presented on this web site. Your algorithm must incorporate at least the following topics:

    • Create a large stack to store index pairs. Index generation occurs within the stack class as needed during idle periods. Background stack operations (FIFO) including index pair generations are transparent to surrounding processes. (Reference exercises 1 & 15 above for implementation details.)

    • Incorporate a greedy algorithm strategy. For instance, the distance of all cities along the tour including a return path can be initially arranged in ascending order based on the current city (or starting point), then permute the list of cities and recalculate distance(s) until a shortest path is discovered within a reasonable time. Adding the first new city from the best-discovered tour held above is one step forward toward the overall goal. The new discovered city becomes the current city (or starting point) and the process repeats itself until all cities are explored. Consider all cities that must be part of your view within a reasonable time-frame. Initially consider a wide radius centered upon the home city utilizing the QuickPerm algorithm to create two pathways that will eventually connect to complete the tour. Head and tail strategies may also be considered for this exercise.

    • Implement time management procedures. For large tours, determine a maximum permutation time and when to utilize the best-discovered tour held. Fortunately the permutation presented in QuickPerm focuses upon the head of the array and initially avoids obvious irrational tours. (Reference exercise 5 above.)



  19. Notice the Meta-Permutation class stems from the countdown QuickPerm algorithm and allows free public access to the four indices: j, i, q, & r. Rewrite the Meta-Permutation class using the counting QuickPerm algorithm (as a new origin) and declare the four indices private. In addition, convert Example_02, Example_03, and Example_04 to counting QuickPerm algorithms (respectively) without loosing the original intent. (Partially solved by Nick Fahrenholtz)


  20. Create three new public functions for the Meta-Permutation class (Example_05). Each function will adjust the primary controller array p[N] in order to reset, rewind, and fast-forward index pair calculations. The reset() function will simply reinitialize the primary controller array p[N] to corresponding index values or to zero depending on the constructor class implemented (in relation to a countdown or counting process described previously). No parameter is required for the reset() function.

    Whereas the rewind(n) and FastForward(n) functions require a positive integer parameter to shift an index pair. For example, calling the function rewind(1) recovers from a single next() call and calling the function FastForward(10) is identical to calling the next() function ten consecutive times but without actually swapping elements in the target array. Simple modulus division or a new public integer counter within the MetaPerm class is required to indicate a complete odometer roll-over(s).

    In conjunction with permutation exercises 5, 7, 9, 10, 20, 21, 23, and 26, the Meta-Permutation class can be adapted for distributed processing. To solve these exercises it's important to notice the p[N] controller array's behavior is analogous to an incremental Base-N-Odometer, where digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Utilizing this model, upper and lower indices can easily map to any valid Base-N-Odometer setting. Also recall the primary controller array p[N] can be initialized either to corresponding index values for a countdown process or to zero for a counting process strictly depending upon the programmer's concerns. (Hint: Every Base-N-Odometer reading directly maps to a unique ordered list defined by the programmer and by the initial list given.)


  21. Write two distinct algorithms to perform the following tasks:

    • Algorithm 1: Count each combination without actually generating them (or simply without using recursion compute a previous generation count solely based upon the Base-N-Odometer reading). BIG HINT?

    • Algorithm 2: Quickly compute the nth permutation without generating (n!-1) combinations. Your algorithm must follow the output order from the QuickPerm algorithm (formally Example_01) and compute the exact index order using the array p[N] without swapping elements within the target array a[]. (Hint: Use Algorithm 1 above and the array p[N] to predict the nth permutation. Also recall the p[N] controller array's behavior is analogous to an incremental Base-N-Odometer, where digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N.)

      NOTE: Since the initial publication of this exercise in 1991, several attempts were made to solve Algorithm 2 as described above. Some attempts were very successful and obviously correct, but unfortunately many algorithms found on the Internet today (such as the recent article by Dr. James McCaffrey) mistakenly represent the nth permutation initially as a very limited integer parameter. These algorithms clearly fail for a large n within permutation sets where the length of the linear list or target exceeds 12 elements.

      Accepted solutions to this exercise manually set the Base-N-Odometer then calculate the nth permutation solely based upon the new Base-N-Odometer reading. Utilize the same parameter concept as found in common Factorial functions to set the Base-N-Odometer without calculating a large factorial number(s) as a result. Research the QuickPerm Reversal Algorithm (formally Example 03) and answer Permutation Exercise 9 (above) before attempting to solve this exercise.



  22. Create an improved random number generator called RandPerm using the MetaPerm algorithm and a large Cyclic Redundancy Check (CRC) number. Initially populate the target array a[N] using several well known random number series then compute a large CRC number using the entire target array. Return the large CRC number as a decimal number and SWAP the elements in the target array referenced by the MetaPerm algorithm. Call the MetaPerm public function next() and repeat this process until no user request remains. (Avoid using a standard random number generator based upon "time" to populate the target array or even supplement the random CRC number returned to the user.)

    Answer the following exercises based upon the RandPerm algorithm described above:

    • Describe the influence of N's size when N < 12 and when N >= 12.

    • Calculate a CRC number from an opposite direction. Compare the outcome to the previous method implemented and report noticeable correlations (or patterns).

    • Using the MetaPerm class' public variables j, i, q, and r, alternate swapping elements between the head and the tail of the target array a[N]. Measure the statistical significance (or describe the duplicate sets produced). How would your measurements change by using two or more targets initially?

    • Create a permutation algorithm that cycles or thrashes a new target array and compare it to the RandPerm algorithm developed above. (Hint: Individually increment the Base-N-Odometer's digits cyclically or increment the odometer by a number greater than one.)

    • Describe the benefits (pros and cons) of using a permutation based random number generator instead of using a common random number generator based upon time. Consider several lottery number machines that can automatically pick a number sequence for the customer. Imagine some of these machines are based upon a permutation whereas others are based upon time. What happens when a several customers purchase a ticket at the exact "machine" time? What if there was a single primary index controller array (or just one Base-N-Odometer) that was shared for all permutation based machines? A large casino can also utilize a Base-N-Odometer(s), instead of random events based on time, to control large payouts without loosing the appearance of randomness or luck...

    • Write an essay accurately describing the vital significance of a permutation based random number generator within Artificial Intelligent programs. (HINT: What's the computer doing when it's not trying to solve a problem?)

    • Can you guess my "lucky" number? (Click here for the answer.)


  23. Create a computer algorithm that compares a working graphic Base-N-Odometer p[N] with a permutable target a[N] of corresponding index values. In addition, this algorithm will simultaneously display both counting processes mentioned earlier using a single integer array for the Base-N-Odometer and using two integer arrays for the respective permutable targets. Pause before each swap for at least 3 seconds and highlight the elements that were swapped within the target arrays. Label the upper index pointers then highlight the corresponding lower index odometer digits/wheels referenced.

    For each counting process, exactly describe the correlation between the odometer digits and the actual index order displayed. Also, compute the total number of elements swapped based only upon the Base-N-Odometer. For extra credit, accurately identify odometer settings (digit-by-digit) that directly correspond to a prime number THEN write a Prime Number Generator algorithm (called QuickPrime) by properly setting the Base-N-Odometer and returning a large prime decimal number from the new odometer reading. (Hint: At the outset, identify prime numbers within a large sequential list of Base-N-Odometer readings by counting obvious digit repetitions...)


  24. The performance of Example_03 head reversals and the performance of Example_04 tail reversals can be drastically improved by combining the two nested loops into linear conditional statements as described in the counting QuickPerm algorithm. Combine the two nested loops within these examples, verify the output, then compare various execution times with the five examples presented on this site. In addition, the lower index variable j is replaceable by the value stored in p[i] when the upper index variable i is odd, otherwise the lower index variable j is replaceable by the value stored in p[0]. Prove all optimizations that are universal.


  25. Drastically improve the performance of the Steinhaus-Johnson-Trotter Algorithm (or the SJT Algorithm) by incorporating a Base-N-Odometer. Specifically utilizing the Base-N-Odometer model create (then compare) three algorithms to produce the following permutation sets: The first algorithm will produce a set in lexicographical order (index sorting), the second algorithm will produce a set by transposing adjacent elements (Steinhaus-Johnson-Trotter Algorithm), and the third algorithm will produce a set based upon the output from Albert Nijenhuis' & Herbert S. Wilf's Combinatorial Algorithm(s). Also, NO recursion allowed. (Hint: In addition to formally defining index variables, the Base-N-Odometer must also control the overall iteration process for any large cyclic-permutation. For more information review Example-03.)


  26. Add a private function to MetaPerm that returns the largest permutation subset completed in t seconds. Integrate this function in order to dynamically manage time, to distribute reasonable jobs, and to solve complex problems such as a large tour for the traveling salesman (TSP).


  27. Calculate the number of tasks your personal computer can complete within ten (10) seconds, then utilize Example-03 for multitasking within a similar timeframe. Present all findings in a formal report. (Hint: Confine all tasks within a ten-second Base-N-Odometer range ... a queue of queues.)


  28. Permutation exercise 7 combined head and tail QuickPerm algorithms, but ignored the four indices returned by the Meta-Permutation Class. Incorporate a single MetaPerm object to answer permutation exercise 7 as written above. In addition, consider the following exchanges upon the target array(s): SWAP(a[i], a[q]), SWAP(a[i], a[r]), SWAP(a[j], a[q]), and SWAP(a[j], a[r]). Accurately describe an index adjustment when two indices are equivalent. Again, measure statistical significance using a single target a[] and determine when to halt execution. Be creative and attempt to combine this additional assignment with previous QuickPerm examples in any combination. How would your argument change by using two or more duplicate targets initially? Present all findings in a formal report. (Hint: Generally after progressive research utilizing various forms of the QuickPerm algorithm, numerous innovative generation sequences are discovered...)


  29. Remote controlled locks are extremely vulnerable to electronic eavesdropping devices and consequently devious playback tactics. Precisely describe a method of implementing two auto-synchronized Base-N-Odometers broadcasting dynamic encoded signals. (Hint: Increment or decrement the Base-N-Odometers by a number greater than one and allow the odometers to freely rollover...)


  30. Formally prove both countdown QuickPerm reversal algorithms as presented on this website. Reports shall begin with a broad empirical proof followed by a sound analytical proof. How can a QuickPerm Reversal Algorithm be used to omit duplicate generations within a complete permutation set? (HINT: Compare the QuickPerm Reversal Algorithm to a single-pass Palindrome detection algorithm.)


  31. Modify the counting Meta-Permutation Class presented in exercise 19 by adding four index variables described as follows: define two indices in the MetaPerm constructor for head and tail reversals then declare two additional indices to accurately represent a countdown process. Again all indices are private. Finally, incorporate additional index variables in order to transpose adjacent elements within the target data structures (reference the Steinhaus-Johnson-Trotter Algorithm). For extra credit, create a universal Meta-Permutation Class that provides unique indices for all known generation sequences. (Hint: Fundamentally any generation sequence is possible utilizing the Base-N-Odometer model. In this case, the Base-N-Odometer must control the overall iteration process for a large cyclic-permutation. For more information review permutation exercise 25 above and the notes for Example-03.)


  32. A universal MetaPerm algorithm is capable of calculating and returning various indices for any generation sequence regardless of the target data structure(s) at hand. Accurately describe the correlation of the indices returned and common data structures such as linked-lists, perfect multi-dimensional arrays, tree structures, a queue of queues, and graphs. Provide an operational algorithm and practical examples for each data structure referenced.


  33. The QuickPerm Reversal Algorithms presented on this website are well suited to detect Palindrome substrings within a target array(s). Modify a QuickPerm Reversal Algorithm to omit possible duplicate generations within a complete permutation set. To accomplish this goal, a stated guideline is compromised: The linear permutable target can NOT be examined.


  34. Utilize the Base-N-Odometer model to create a very efficient "Big Integer Calculator". No Stacks Allowed!


  35. Write an intelligent permutation algorithm to solve any given "Rubik's Cube". Obey the rules of Rubik's Cube (3 x 3 x 3 or 5 x 5 x 5) for rotations and swapping colored cubes. (Hint: Examine each side of the cube before applying a focused permutation. Repeat this process for the remaining sides until a solution is reached.)


  36. Use the QuickPerm or the MetaPerm algorithms presented on this web site to solve the puzzle Spinout, manufactured by Binary Arts Corporation. (Hint: Utilize the Base-N-Odometer model.)


  37. Focused permutation efforts, such as the QuickPerm and the MetaPerm algorithms, clearly offer many efficient timesaving advantages. Compare and contrast the QuickPerm and the MetaPerm algorithms to common cyclic permutation algorithms, complex heuristic models, and uncontrollable recursive solutions.


  38. Examination of very large arrays or continuous linear character streams of an unknown length is not feasible utilizing cyclic permutation algorithms or even heuristic approaches. Considering the QuickPerm and the MetaPerm algorithms presented on this web site, discuss a procedure for processing a continuous linear character stream(s).


  39. Discuss the disadvantages of implementing a "Random Permutation". In addition, describe a "Miracle Method" and the relationship to a "Random Permutation" for very large target lists.


  40. Solve the Traveling Salesman Problem for an unknown number of cities. Assume the city coordinates are ordered in the linear stream according to the distance ascending from the salesman's home city (the starting point). (Hints: Expand your view by implementing mathematic annealing processes upon several centralized city coordinates. Overall, approximate a time period to complete this task.)


  41. Text encryption algorithms, including MIME, produce simple printable ASCII characters that can be transmitted within the body of an email message. Utilize a common MIME encryption algorithm to produce a simple text file, THEN feed the output stream into the QuickPerm algorithm. Allow the user to enter a Personal Identification Number (or PIN) that advances the Base-N-Odometer for each character stuffed into the target array. Overflow from the target array is returned as output. (HINT: Initialize the target array to NULL, then choose a consistent entry point to stuff the array. Keep the size of the target array less than fifteen and allow the corresponding parallel Base-N-Odometer to freely rollover.)


  42. The Permutation Clock can also be described as a clock's pendulum. Compose a five-page essay with several illustrations to accurately describe a pendulum analogy and perpetual improvements within any computer application over time.


  43. Write a computer program to simultaneously display (graphically) a Permutation Clock and a Pendulum along with a scrolling Permutation Ruler.



Why not contact the author and make a donation today?


Chapter 12: Miscellaneous Internet Hyper-Links
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.



Research with GOOGLE.COM
Google


Please send me an email if you find something new and exciting on the net.


Appendix: Famous Permutation Algorithms

{Work~In~Progress}