Scalable Permutations: A Permutation of Agreeable Ideas (PREVIEW)
By Phillip Paul Fuchs
{menu} {mirror}
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 "Catch22" 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
Chapter 1: Permutation Odometers
The BaseNOdometer 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 odometerstyle 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 fastforward(n)  solely based upon an odometer reading?
As stated before, the "BaseNOdometer" 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 BaseNOdometer (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 BaseNOdometer, 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[N1] 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 "BaseNOdometer", a standard automobile trip odometer, and an odometerstyle generator commonly referenced by modern lexicographical (alphapermutation) 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 FastForward(n) 
Yes 
??? 
??? 
Calculate the Nth Combination 
Yes 
??? 
??? 
Miscellaneous / Other 
??? 
??? 
??? 
For more information on the BaseNOdometer research the countdown QuickPerm algorithm followed by the counting QuickPerm algorithm.
Glossary: {Compare and contrast the following vocabulary terms as presented below.}
BaseNOdometer noun
 a core algorithm primarily used to count all generations within a permutation set containing N elements or used as a Big Integer Calculator.
 an algorithm for recording numerous events over time by counting in a sequentially based numbering system.
 an algorithm for counting events within a fixed time period that can be initialized, reset, rewound, or advanced.
 an algorithm for sequentially counting events exceptionally characterized by occurrences of duplicate digits and digit rollovers.
 an algorithm used to identify valid target elements within a parallel linear list(s) or used to determine a pending event.
Odometer noun
 an instrument used to measure distance traveled.
 an instrument for recording an overall distance traveled counting in a universal base 10 numbering system.
 an instrument for measuring a distance traveled between two geographic coordinates. Often referenced as a tripodometer.
 an instrument for measuring distance traveled by a sequential count characterized by occurrences of duplicate digits and digit rollovers.
 an instrument used to determine a scheduled event or repair.
Permutation Odometer noun
 an algorithm used to count all generations within a permutation set containing N elements. Also called the "BaseNOdometer".
 an algorithm for recording unique generations processed by counting in a sequentially based numbering system.
 an algorithm for counting generations over a fixed time period within a permutation set that can be initialized, reset, rewound, or advanced.
 an algorithm for sequentially counting generations exceptionally characterized by occurrences of duplicate digits and digit rollovers.
 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 homosapiens 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 BaseNOdometer by one produces an ending for a known permutation set.
Incrementing the BaseNOdometer by one again produces an ending for another known permutation set; and so on until the current permutation set is exhausted...
Each BaseNOdometer 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 BaseNOdometer reading) to produce a desired generation sequence.
Fundamentally any generation sequence is possible utilizing the BaseNOdometer model, but often there are tradeoffs.
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 MetaPermutation 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 BaseNOdometer 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 bruteforce 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 wellknown 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 NPComplete 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 32bit 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 BaseNOdometer 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 PseudoCode 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)

~ Comparable PseudoCode 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[N1] 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 "BaseNOdometer" next.
Comparable PseudoCode Representations
~ PseudoCode 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)

~ PseudoCode 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[N1] to N1
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)

~ PseudoCode 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)

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 50element 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 51element array would complete in approximately:
10 Seconds * 51 = 510 Seconds or 8.5 Minutes
A permutation over a new 52element 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 53element array would complete in approximately:
10 Seconds * 51 * 52 * 53 = 1405560 Seconds or 16.27 Days
A permutation over a new 54element array would complete in approximately:
10 Seconds * 51 * 52 * 53 * 54 = 75900240 Seconds or 2.41 Years
A permutation over a new 55element 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 53element array. Using an array with more than 53elements 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
QuickPerm  Function to Display Permutations (Optional)
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 inturn 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:
 Initializing all integers in the controller array to corresponding index values.
 Decrement p[i] by one before the conditional assignment j = p[i]
 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 ifelse statement (as described in the counting QuickPerm algorithm) clearly lead to the development of a Metapermutation class.
Although this conditional substitution can be made regardless of the counting process utilized, the Metapermutation 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 inturn 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
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[N1] 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:
 Initializing all integers in the controller array to zero.
 Increment p[i] by one after the conditional assignment j = p[i]
 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 ifelse statement, which inturn 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
QuickPerm  Function to Display Permutations (Optional)
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
EXAMPLE 02a  Function to Display Permutations (Optional)
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 BaseNOdometer 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 midpoint here is easily defined as well).
To illustrate the versatility of the BaseNOdometer (or the core), consider the following PseudoCode representation:
~ Countdown QuickPerm Reversals (PseudoCode) ~
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 BaseNOdometer
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 BaseNOdometer
let p[i] = i
increment i by 1
} // end while (p[i] is equal to 0)
} // end while (i < N)

Recall that each BaseNOdometer 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 BaseNOdometer reading) to produce a desired generation sequence.
Fundamentally any generation sequence is possible utilizing the BaseNOdometer model, but often there are tradeoffs.
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 BaseNOdometer 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 BaseNOdometer, 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 inturn 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 BaseNOdometer 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 WALA
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
EXAMPLE 03a  Function to Display Permutations (Optional)
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 singlepass 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
EXAMPLE 04a  Function to Display Permutations (Optional)
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 MetaPermutation class supplies head and tail indices to EXAMPLE 05, which is next on our tour...
Chapter 5: The Universal MetaPermutation 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 Metapermutation 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 Metapermutation class (below).
In contrast, replacing the nested while loop with a conditional ifelse statement as described in the
counting QuickPerm algorithm causes the Metapermutation 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 MetaPermutation Class precludes such a substitution in order to return valid indices.
Example_05 efficiently combines the four previous examples by utilizing a single MetaPermutation Class aptly named MetaPerm. Here's the MetaPermutation Class written in C++ for your review:
MetaPerm Class  Combining the Four Previous Examples
MetaPerm Function to Display Permutations (Optional)
Now try downloading the five C++ examples and solving the permutation exercises.
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 endresult is often a wellplanned computer application focused upon a specific solution.
Application upgrades often stem from user demands directly fedback 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:
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 fuchs@teacher.com {click here}. All serious attempts will receive a reply and solution (NO homework projects). Please consider giving a taxdeductible donation.
 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.)
 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.)
 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.
 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.)
 Describe possible improvements for each Example presented. Include in your essay descriptions on
divide & conquer,
dynamic programming,
distributed processing, and time management procedures.
 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.)
 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 headhead scenario and four (4) distinct sets produced for each tailtail scenario.
For extra credit, consider dividing the target array in half by using a tailhead 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 overindexing an array...)
 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.)
 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[N1] 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]), afterwhich 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 midpoint *~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.)
 Modify the MetaPerm object (EXAMPLE_05) for distributed processing.
 Discuss the impact of converting the MetaPerm class to a hardware solution.
 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.
 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.
 Provide a formal algorithm analysis for both QuickPerm algorithms. For this exercise, calculate the approximate running time of QuickPerm in BigO 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.)
 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.)
 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);
...
 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.
 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 bestdiscovered 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 timeframe. 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 bestdiscovered 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.)
 Notice the MetaPermutation class stems from the countdown QuickPerm algorithm and allows free public access to the four indices: j, i, q, & r.
Rewrite the MetaPermutation 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.
 Create three new public functions for the MetaPermutation class (Example_05). Each function will adjust the primary controller array p[N] in order to reset, rewind, and fastforward 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 rollover(s).
In conjunction with permutation exercises 5, 7, 9, 10, 20, 21, 23, and 26, the MetaPermutation 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[N1] 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.)
 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[N1] 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 BaseNOdometer then calculate the nth permutation solely based upon the new BaseNOdometer reading.
Utilize the same parameter concept as found in common Factorial functions to set the BaseNOdometer 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.
 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.)
 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 (digitbydigit) 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...)
 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.
 Drastically improve the performance of the SteinhausJohnsonTrotter Algorithm (or the SJT Algorithm) by incorporating a BaseNOdometer.
Specifically utilizing the BaseNOdometer 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 (SteinhausJohnsonTrotter 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 BaseNOdometer must also control the overall iteration process for any large cyclicpermutation. For more information review Example03.)
 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).
 Calculate the number of tasks your personal computer can complete within ten (10) seconds, then utilize Example03 for multitasking within a similar timeframe.
Present all findings in a formal report.
(Hint: Confine all tasks within a tensecond Base N Odometer range ... a queue of queues.)
 Permutation exercise 7 combined head and tail QuickPerm algorithms, but ignored the four indices returned by the MetaPermutation 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...)
 Remote controlled locks are extremely vulnerable to electronic eavesdropping devices and consequently devious playback tactics.
Precisely describe a method of implementing two autosynchronized 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...)
 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 singlepass Palindrome detection algorithm.)
 Modify the counting MetaPermutation 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 SteinhausJohnsonTrotter Algorithm).
For extra credit, create a universal MetaPermutation 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 cyclicpermutation.
For more information review permutation exercise 25 above and the notes for Example03.)
 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 linkedlists, perfect multidimensional arrays, tree structures, a queue of queues, and graphs.
Provide an operational algorithm and practical examples for each data structure referenced.
 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.
 Utilize the Base N Odometer model to create a very efficient "Big Integer Calculator". No Stacks Allowed!
 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.)
 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 BaseNOdometer model.)
 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.
 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).
 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.
 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.)
 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 BaseNOdometer 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 BaseNOdometer to freely rollover.)
 The Permutation Clock can also be described as a clock's pendulum.
Compose a fivepage essay with several illustrations to accurately describe a pendulum analogy and perpetual improvements within any computer application over time.
 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 HyperLinks
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.cuttheknot.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 "JohnsonTrotter" Algorithm:
The JohnsonTrotter 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 SteinhausJohnsonTrotter 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 NijenhuisWilf 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 minimumchange order. Click here for the actual FORTRAN example of the NijenhuisWilf algorithm published circa 1975.
The SEPA Algorithm:
The SEPA algorithm by Jeffrey A. Johnson at the Brigham Young UniversityHawaii 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,509city tour through the United States (solved in 1998), they presented another solution for a 15,112city 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 (FiniteState 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
Please send me an email if you find something new and exciting on the net.
Appendix: Famous Permutation Algorithms
{Work~In~Progress}
{top}
Copyright © 2010 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...