• PREFACE: Scalable Permutations ~ "A Permutation of Agreeable Ideas"
  
  

• Chapter  1: Permutation Odometers ~ The Base-N-Odometer Model

• Chapter  2: Countable Permutations ~ Historic Permutation Algorithms

• Chapter  3: Scalable Permutations ~ The Five Guiding Principles

• Chapter  4: The QuickPerm Algorithms ~ Counting and Countdown Solutions

• Chapter  5: The MetaPerm Algorithm ~ A Universal Solution

• Chapter  6: Solving the Unsolvable ~ Solving NP-Complete Problems Incrementally

• Chapter  7: Problem Distribution ~ Following Every Lead

• Chapter  8: The Permutation Clock ~ Perpetual Improvements

• Chapter  9: Iteration ~ VS ~ Recursion

• Chapter 10: Analysis of the QuickPerm and MetaPerm Algorithms

• Chapter 11: Permutation Exercises

• Chapter 12: Miscellaneous Internet Hyper-Links ~ More Permutation Methods to Explore
  
  

• Appendix: Famous Permutation Algorithms

Scalable Permutations Preface:
"A Permutation of Agreeable Ideas"

What's more important? "The permutation of agreeable ideas or the common synchronization response to a proven solution."

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

Are we there yet?

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

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

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.

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.

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

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 linear array permutations 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:

	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.)
	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.
	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...and all sets are countable!
	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...
	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!

   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)

   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)

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

   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)

   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)

   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)

Chapter 4: The QuickPerm Algorithms

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

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

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

QuickPerm - Head Permutations Using a Linear Array Without Recursion

// NOTICE: Copyright 1991-2008, 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-2008, 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	1 2 3	3 2 1                      {Output}	2 * 3 = 6
4	1 2 3 4	4 1 2 3                   {Output}	6 * 4 = 24
5	1 2 3 4 5	5 2 3 4 1                {Output}	24 * 5 = 120
6	1 2 3 4 5 6	6 3 4 1 2 5	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	8 3 4 5 6 1 2 7	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 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:


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

(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

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.

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

// NOTICE: Copyright 2008, 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 2008, 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

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:


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-2008, 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-2008, 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)

   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)

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

Example_03 - Permutation Reversals on the Head of a Linear Array Without Using Recursion

// NOTICE: Copyright 1991-2008, 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-2008, 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)


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

// NOTICE:  Copyright 1991-2008, 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--;
         //display(ex3);       // remove comment to display permutations using head reversals

         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++;
         //display(ex4);       // remove comment to display permutations using tail reversals
      } while (s.j < s.i);  // or while(s.q < s.r);
      s.next();    // create new index values for another unique exchange
   } // while (s.i < N)
} // example_05()

// NOTICE:  Copyright 1991-2008, 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()

Chapter 6: Solving the Unsolvable

Chapter 7: Problem Distribution

Chapter 8: The Permutation Clock
By Phillip Paul Fuchs

Chapter 9: Iteration ~ VS ~ Recursion

Chapter 10: Analysis of the QuickPerm and MetaPerm Algorithms

Chapter 11: Permutation Exercises

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 calculation of q() Theta and the lower bound W() 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.

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.

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:
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://turing.wins.uva.nl/ 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://turing.wins.uva.nl/ 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.catbrandywine.org/ for more information about the Center for Arts and Technology at the Brandywine campus.

Research with GOOGLE.COM

Appendix: Famous Permutation Algorithms