{menu} {mirror}

Removing the Nested While Loop...

The extra credit for exercise two addresses the possibility of replacing the nested while loop with a well planned mathematic equation or a primary binary sequence. One transposition (or swap) is immediately followed by a calculation of the upper index boundary with no conditional divisions.

The extra credit for exercise two does not address the possibility of alternate solutions focused upon conditional branch statements. The pseudo-code listed below describes such a valid method for substituting the nested while loop with alternate conditional operators:


~ A Pseudo-Code Representation ~
   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[N-1] to N-1
   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)

Who said extra credit was an unwrapped gift? Click here to return to permutation exercise number 2.