{menu} {mirror}

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

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

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

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

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

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

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