{menu} {mirror}

(Countdown) QuickPerm Tail Reversals:
(Formally EXAMPLE_04)

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

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

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

   for(i = 0; i < N; i++)   // initialize arrays; a[N] can be any type
   {
      a[i] = N - i;   // a[i] value is arbitrary and not revealed
      p[i] = N - i;
   }
   //display(a);   // remove comment to display array a[]
   i = ax;   // setup first swap point to be ax
   while (i > 0)
   {
      p[i]--;             // decrease index "weight" for i by one
      i--;                // i must be less then j (i < j)
      j = ax;             // reset j to ax
      do                  // reverse target array from i to j
      {
         tmp = a[j];      // swap(a[i], a[j])
         a[j] = a[i];
         a[i] = tmp;
         j--;             // decrement j by 1
         i++;             // increment i by 1
      } while (j > i);
      //display(a);       // remove comment to display target array a[]
      i = ax;             // reset index i to ax (assumed)
      while (!p[i])       // while (p[i] == 0)
      {
         p[i] = N - i;    // reset p[i] zero value
         i--;             // set new index value for i (decrease by one)
      } // while (!p[i])
   } // while (i > 0)
} // example_04()
EXAMPLE 04a - Function to Display Permutations (Optional) 
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs                         

void display(unsigned int *a)
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("\n");
   getch();  // press any key to continue...
} // display()
Fundamental Analysis of Permutation Example 04 Above
Number of Objects
to Permute (N)		 a[N] Display of
Initial Sequence		 a[N] Display of
Final Sequence		 Total Number of Unique
Combinations Produced (N!)
3 3 2 1 1 2 3 2 * 3 = 6
4 4 3 2 1 1 2 3 4 6 * 4 = 24
5 5 4 3 2 1 1 2 3 4 5 24 * 5 = 120
6 6 5 4 3 2 1 1 2 3 4 5 6 120 * 6 = 720
7 7 6 5 4 3 2 1 1 2 3 4 5 6 7 720 * 7 = 5040
8 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 5040 * 8 = 40320
9 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 40320 * 9 = 362880
N N (N - 1) . . . 3 2 1 1 2 3 . . . (N - 1) N (N - 1)! * N = N!

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