{menu} {mirror}

The Countdown Meta-Permutation Class:
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. Visit original 1986-91 algorithm solution by P. Fuchs)

Presented below is the C++ algorithm which answered Dr. Milito's question proposed sometime during 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 Meta-permutation object m(N), SWAP(h[m[J]], h[m[I]]) is valid for all head combinations whereas SWAP(t[m[Q], t[m[R]]) is valid for all tail combinations provided that all SWAP calls are followed by a single m.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 Meta-permutation class (below). In contrast, replacing the nested while loop with a conditional if-else statement as described in the counting QuickPerm algorithm causes the Meta-permutation 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 Meta-Permutation Class precludes such a substitution in order to return valid indices.

Example_05 efficiently combines the four previous examples by utilizing a single Meta-Permutation Class aptly named MetaPerm. Here's the Meta-Permutation Class written in C++ for your review:


MetaPerm Class - Combining the Four Previous Examples as One 
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs
//          2010 Modifications by Nick Fahrenholtz

#define N    12   // number of elements to permute.  Let N > 2
enum { I, J, Q, R };

class MetaPerm {
        unsigned int i, j, q, r, *p, ax;   // declare indexes for head and tail combination
    public: 
        unsigned int operator[](int i);    // Overload [] to read private index variables
        inline void next(void);            // calculate new indexes for head and tail combination
        MetaPerm(unsigned int n);          // initialize first set of indices (i, j, q, & r)
        ~MetaPerm(void) { delete [] p; };
};

MetaPerm::MetaPerm(unsigned int n) { // MetaPerm(unsigned int) Constructor (Initialize or Reset Odometer)
   p = new unsigned int[n+1];  // declare Base-N-Odometer array for primary index controller
   for(j = 0; j <= n; j++)     // initialize the Base-N-Odometer array for a countdown process
      p[j] = j;

   i = 1;                      // initialize head indices i & j
   j = 0;
   ax = n - 1;                 // define index ceiling
   q = ax - i;                 // initialize tail indices q & r
   r = ax - j;
   p[1] = 0;                   // Record initialization event of indices above
} // end MetaPerm(unsigned int) Constructor (Initialize or Reset Odometer)

void MetaPerm::next(void) 
{ // Control Threading Here
   i = 1;                      // reset index i to 1 (assumed)
   while (!p[i]) {             // while (p[i] == 0)
      p[i] = i;                // reset p[i] zero value
      i++;                     // set new index value for i (increase by one)
   }
   p[i]--;                     // decrease index "weight" for i by one
   j = i % 2 * p[i];           // IF i is odd then j = p[i] otherwise j = 0
   q = ax - i;                 // adjust tail indices q and r such that q < r
   r = ax - j;
} // end MetaPerm::next()


unsigned int MetaPerm::operator[](int i) {
       return ((int*)this)[i % 4];
} 


/*******************************************************************************************/
/*******************************************************************************************/


int main(void) {
    unsigned int ex[N];
    register unsigned int tmp;
    { // Sub-scope for QuickPerm examples 1 & 2
        MetaPerm m(N);
        unsigned int ex2[N];
        for(unsigned int i = 0; i < N; i++) { // initialize arrays for combination
            ex[i]  = i + 1;
            ex2[i] = ex[i];
        }
        //display(ex);  // remove comment to display head combination
        //display(ex2); // remove comment to display tail combination
        
        while (m[I] < N) {
            tmp = ex[m[J]];      // swap(ex[m[I]], ex[m[J]])
            ex[m[J]] = ex[m[I]];
            ex[m[I]] = tmp;
            //display(ex);         // remove comment to display head combination
            
            tmp = ex2[m[R]];     // swap(ex2[m[Q]], ex2[m[R]])
            ex2[m[R]] = ex2[m[Q]];  
            ex2[m[Q]] = tmp;
            //display(ex2);        // remove comment to display tail combination
            m.next();              // create new index values for another unique exchange
        }
    } // MetaPerm m and int ex2 are now undefined

    { // Sub-scope for QuickPerm example 3
        MetaPerm m(N);           // demonstration of combinations using reversals 
        unsigned int j, i;
        for(unsigned int i = 0; i < N; i++) // initialize array for combination
            ex[i] = i + 1;
        
        //display(ex);   // remove comment to display combination using head reversals
        while (m[I] < N) {
             j = 0;              // establish lower range for head reversals
             i = m[I];
            do {
                tmp = ex[j];     // reversal of array head from 0 to m[I]
                ex[j] = ex[i];  
                ex[i] = tmp;
                j++; i--;
            } while(j < i);
            //display(ex);   // remove comment to display combination using head reversals
            m.next();            // create new index values for another unique exchange
        }
    } // i, j, and m are now undefined

    { // Sub-scope for QuickPerm example 4
        MetaPerm m(N);           // demonstration of combination using reversals 
        unsigned int q, r;
        for(unsigned int i = 0; i < N; i++) // initialize arrays for combination
            ex[i] = i + 1;
        
        //display(ex);   // remove comment to display combinations using tail reversals
        while (m[I] < N) {
            q = m[Q];          // establish upper range for tail reversals
            r = N - 1;
          
            do {
                tmp = ex[r];     // reversal of array tail from m.get().q to (N-1)
                ex[r] = ex[q];
                ex[q] = tmp;
                q++;  r--;
            } while(q < r);
            //display(ex);   // remove comment to display combination using tail reversals
            m.next();            // create new index values for another unique exchange
        } // while (m.get().i < N)
    } // q, r, and m are now undefined
} // main()


MetaPerm Function to Display Permutations (Optional) 
// NOTICE:  Copyright 1991-2010, Phillip Paul Fuchs                                          
//          2010 Modifications by Nick Fahrenholtz

static void display(unsigned int *a)
{
   for(unsigned int x = 0; x < N; x++)
      printf("%d ",a[x]);
   printf("\n");
} // display()

Now try downloading the five C++ examples and solving the permutation exercises.





Permutation Clock