{menu}

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

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


~ Countdown QuickPerm Reversals (Pseudo-Code) ~

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



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

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

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

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

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

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

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

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

// NOTICE:  Copyright 1991-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)
A Permutation Ruler

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

[New Book: Practical Permutations]

[QuickPerm] | [EXAMPLE 02] | [EXAMPLE 03] | [EXAMPLE 04] | [MetaPerm]
[Download the Five C++ Examples] | [Permutation Exercises]
[Contact the Author] | [Make a Donation] | [Links]
[HOME]

Help keep public education alive! We need your donations, click here to help now...

{top}

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