Permutation Exercises:

1. For every odd reference call, index values of a 0 and a 1 are produced. Improve the performance of QuickPerm (EXAMPLE_01) by alternating between two functions. Calling one function will simply return a 0 and a 1, whereas calling the second function will calculate new index values. (Your output will remain the same as the original.)

2. QuickPerm (EXAMPLE_01) computes the index value of j using the following line:

j = i % 2 * p[i];

Rewrite this line to improve performance. Time each improvement and present your findings in a table format. (HINT: Addition is much faster than multiplication.)

For extra credit, remove the nested while loop and compute the second index value i. Try replacing the nested loop with a fractal equation that depends upon the established range and the first index value generated. (A very large integer or binary operations will also work in this case.)

3. Rewrite EXAMPLE_02 using recursion and compare it to the efficiency of using iteration. Although recursion and iteration are theoretically equivalent, converting an iterative algorithm to a recursive one is difficult and sometimes impossible. Begin by using a known recursive algorithm and attempt to modify it.

4. Did you actually purchase a computer that was three times the speed of your old computer? Is Moore's Law accurate or is Dr. Gordon E. Moore just a wise salesman? Here's your chance to prove it before buying your next computer!

Write an algorithm to accurately time each Example for five different lengths of permutation sets. Be consistent for each Example and do not use a time less than a second more than once. (If you gather times for N as 10, 11, 12, 13, and 14 for QuickPerm (formally EXAMPLE_01), you must use the same values for the remaining four Examples.) Also, predict the amount of time it would take to permute 50, 75, and 100 items. Present your findings in a table format and save them. Repeat this process using a different CPU speed and compare your findings. (Include an accurate description of the advertised speed of each computer that you used for this exercise.)

5. Describe possible improvements for each Example presented. Include in your essay descriptions on divide & conquer, dynamic programming, distributed processing, and time management procedures.

6. Using EXAMPLE_03 and EXAMPLE_04, rewrite and reintegrate the display() function such that an actual reversed range is displayed after the permutation set. Follow QuickPerm (formally EXAMPLE_01) and EXAMPLE_02 display() function, but instead of showing the two indexes that were SWAPPED; simply present the two index values as a range that were REVERSED. (For clarity, change the display() function for all five Examples to output proper set notation.)

7. The concept of a permutation ruler as described in the QuickPerm algorithm combined with Example_02's tail combinations is comparable to a "zipper". Write a new application that combines the QuickPerm algorithm head permutation set with Example_02 tail permutation set. Recall that only when the upper index is odd, a counting process causes the lower index variable to begin at zero then advance by one; whereas a countdown process causes the lower index variable to begin at one less than the current upper index then reduce by one. Four (4) distinct permutation sets (with obvious duplications) are produced by utilizing a combination of both counting and countdown processes. Using a single target a[], measure statistical significance (describe the duplicate items produced) and when to halt execution. How would your argument change by using two or more duplicate targets initially?
   
   In addition, implement mutually exclusive head and tail combinations upon each half of the target array. Be creative here. Again accurately measure statistical significance, but in this case there will be four (4) distinct sets produced for each head-head scenario and four (4) distinct sets produced for each tail-tail scenario. For extra credit, consider dividing the target array in half by using a tail-head scenario where the midpoint is shared respectively. Present ALL your findings in a formal report.
   
   Repeat this exercise combining EXAMPLE_03 head reversals with EXAMPLE_04 tail reversals. Is the counting process relevant? Why or why not? (Overall Hint: Be creative, there are more countable sets to consider especially when over-indexing an array...)

8. Following EXAMPLE_04, rewrite EXAMPLE_02 and MetaPerm (EXAMPLE_05) such that index values are not simply adjusted. (In EXAMPLE_02, the length of the index control array p[] must equal N and not N+1.)

9. Notice the p[N] controller array's behavior is analogous to an incremental base N odometer, where the least significant digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Utilizing this model, upper and lower indices can easily map to any valid base N odometer setting. To illustrate this principle, consider the following (counting) Base N Odometer reading:
   

   
       10!     9!    8!    7!    6!    5!    4!    3!    2!    1!    0!  <- Factorial Base
   3628800 362880 40320  5040   720   120    24    06    02    01    01  <- Positional Value
     p[10]  p[09] p[08] p[07] p[06] p[05] p[04] p[03] p[02] p[01] p[00]  <- Base N Odometer Array
   --------------------------------------------------------------------
   
      {01}   {00}  {00}  {07}  {03}  {02}  {04}  {00}  {01}  {01}  {00}  <- Base N Odometer Reading
   

   
   Solely based upon the odometer reading above, exactly 3,666,579 swap() calls were performed on the target data structure(s). The upper index returned an odd value 1 and the lower index returned 0 (or the current value stored in p[1]), after-which a swap was called and p[1] advanced by one. Before the next swap call, the upper index pointer will flip the odd p[1] digit then settle upon the even p[2] digit and as a result the lower index will be assigned to the value stored in p[0] (or zero). Eventually a swap(0, 2) is called then p[2] advances by one...
   
   The above swap() call calculation (3,666,579) is similar to converting any base number to another base, such as a binary to decimal base conversion. Reading the Base N Odometer (above) from left to right, a current generation count (excluding the original) is calculated as follows:

   
   (1 * 10!) + (7 * 7!) + (3 * 6!) + (2 * 5!) + (4 * 4!) + (1 * 2!) + (1 * 1!)
   

   
   Given the following six incremental base 10 odometer readings for a counting QuickPerm algorithm, calculate the current generation count, determine the upper and lower index values then compute the next odometer setting after a SWAP() is called:

   
   -------------------------------------------------
   p[9] p[8] p[7] p[6] p[5] p[4] p[3] p[2] p[1] p[0]
   -------------------------------------------------
   
   {00} {04} {04} {06} {01} {00} {02} {02} {01} {00}
   
   
   {09} {00} {01} {03} {00} {01} {03} {02} {01} {00}
   
   
   {00} {00} {00} {00} {00} {00} {00} {00} {00} {00}
   
   
   {08} {08} {07} {06} {05} {04} {03} {02} {01} {00}
   
   
   {09} {08} {07} {06} {05} {04} {03} {02} {01} {00}
   
   
   {09} {08} {05} {03} {02} {04} {03} {02} {01} {00}
   

   
   Repeat this exercise using the countdown QuickPerm algorithm then advance the fifth odometer reading (above) for thirty SWAP() call iterations.
   
   Also using both counting methods, accurately describe the Base N Odometer reading at the beginning, at the mid-point *~KEY~*, at the end, and at the exact reverse order. (Hint: Review the fundamental analysis of the QuickPerm algorithms when permutable subset lengths are even and odd.)

10. Modify the MetaPerm object (EXAMPLE_05) for distributed processing.

11. Discuss the impact of converting the MetaPerm class to a hardware solution.

12. Sometimes optimizing the compiler and disabling the video output will increase performance. Implement and document five optimizations that significantly improve performance for all the Examples presented. Follow the guidelines presented at Programming Optimization by Paul Hsieh.

13. Rewrite QuickPerm (EXAMPLE_01) and MetaPerm (EXAMPLE_05) in a programming language(s) of your choice. Compare the efficiency of the Class object presented in MetaPerm with the QuickPerm algorithm as written. Before rewriting and timing these algorithms, modify MetaPerm (without removing the Class) to produce the exact results as QuickPerm. Present your findings in a formal report.

14. Provide a formal algorithm analysis for both QuickPerm algorithms. For this exercise, calculate the approximate running time of QuickPerm in Big-O notation O(), including a strict calculation of q() Theta and the lower bound W() Omega. (This exercise will also help you answer the extra credit presented in exercise #2.)

15. Generating and storing indices without swapping elements in the target array significantly improves performance. Unfortunately, to store individual index sets as two integers would consume a vast amount of memory. Therefore, a binary storage method must be considered and carefully developed. By using simple binary operators, one can create a binary stack (FIFO) directly related to index counters. For example, '10110101101' represents the first 5 index values for i found in QuickPerm (formally EXAMPLE_01). To minimize memory requirements, utilize repeating patterns and consider several segmented binary stacks for each index. Ending i's binary segment depends upon if j is greater than 0 (as seen above). Binary stack operations and segments are transparent to the overall process.

Rewrite QuickPerm (EXAMPLE_01) and implement a binary storage method for both indices. Provide a fundamental analysis for all storage requirements. (Try describing a relationship between each binary number segment and prime numbers.)

16. Encryption algorithms depend upon password(s) to scramble data files. Advanced encryption algorithms avoid repeating patterns within the data file by applying various methods to extend the length of a user's password (unique like pi). Write an algorithm to encrypt or decrypt a file by permuting the user's password. Also, consider incorporating binary operations (an exclusive OR), password rotation, and Cyclic Redundancy Check (CRC) numbers.

For instance, assume you are modifying QuickPerm and the user's password is stored in the character string a[]. Consider expanding upon the following C++ statements to encode a data character from a file's IO stream:

...
swap(a[j], a[i]);
read(data_ch);
new_ch = a[j] ^ CRC(a) ^ data_ch;
save(new_ch);
...



17. Using all 26 lowercase letters in the alphabet, write a program to produce all five letter words. Also, highlight all valid words that are prime. Study the Countdown QuickPerm Reversal Algorithm (Example_03) to produce combinations of 5 letter groups from 26 letters.

18. Solve the traveling salesman problem (TSP) using the QuickPerm algorithms presented on this web site. Your algorithm must incorporate at least the following topics:

• Create a large stack to store index pairs. Index generation occurs within the stack class as needed during idle periods. Background stack operations (FIFO) including index pair generations are transparent to surrounding processes. (Reference exercises 1 & 15 above for implementation details.)

• Incorporate a greedy algorithm strategy. For instance, the distance of all cities along the tour including a return path can be initially arranged in ascending order based on the current city (or starting point), then permute the list of cities and recalculate distance(s) until a shortest path is discovered within a reasonable time. Adding the first new city from the best-discovered tour held above is one step forward toward the overall goal. The new discovered city becomes the current city (or starting point) and the process repeats itself until all cities are explored. Consider all cities that must be part of your view within a reasonable time-frame. Initially consider a wide radius centered upon the home city utilizing the QuickPerm algorithm to create two pathways that will eventually connect to complete the tour. Head and tail strategies may also be considered for this exercise.

• Implement time management procedures. For large tours, determine a maximum permutation time and when to utilize the best-discovered tour held. Fortunately the permutation presented in QuickPerm focuses upon the head of the array and initially avoids obvious irrational tours. (Reference exercise 5 above.)

19. Notice the Meta-Permutation class stems from the countdown QuickPerm algorithm and allows free public access to the four indices: j, i, q, & r. Rewrite the Meta-Permutation class using the counting QuickPerm algorithm (as a new origin) and declare the four indices private. In addition, convert Example_02, Example_03, and Example_04 to counting QuickPerm algorithms (respectively) without loosing the original intent.

20. Create three new public functions for the Meta-Permutation class (Example_05). Each function will adjust the primary controller array p[N] in order to reset, rewind, and fast-forward index pair calculations. The reset() function will simply reinitialize the primary controller array p[N] to corresponding index values or to zero depending on the constructor class implemented (in relation to a countdown or counting process described previously). No parameter is required for the reset() function.
    
    Whereas the rewind(n) and FastForward(n) functions require a positive integer parameter to shift an index pair. For example, calling the function rewind(1) recovers from a single next() call and calling the function FastForward(10) is identical to calling the next() function ten consecutive times but without actually swapping elements in the target array. Simple modulus division or a new public integer counter within the MetaPerm class is required to indicate a complete odometer roll-over(s).
    
    In conjunction with permutation exercises 5, 7, 9, 10, 20, 21, 23, and 26, the Meta-Permutation class can be adapted for distributed processing. To solve these exercises it's important to notice the p[N] controller array's behavior is analogous to an incremental base N odometer, where digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Utilizing this model, upper and lower indices can easily map to any valid base N odometer setting. Also recall the primary controller array p[N] can be initialized either to corresponding index values for a countdown process or to zero for a counting process strictly depending upon the programmer's concerns. (Hint: Every Base N Odometer reading directly maps to a unique ordered list defined by the programmer and by the initial list given.)
    

21. Write two distinct algorithms to perform the following tasks:

• Algorithm 1: Count each combination without actually generating them (or simply without using recursion compute a previous generation count solely based upon the Base N Odometer reading). BIG HINT?

• Algorithm 2: Quickly compute the nth permutation without generating (n!-1) combinations. Your algorithm must follow the output order from the QuickPerm algorithm (formally Example_01) and compute the exact index order using the array p[N] without swapping elements within the target array a[]. (Hint: Use Algorithm 1 above and the array p[N] to predict the nth permutation. Also recall the p[N] controller array's behavior is analogous to an incremental base N odometer, where digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N.)
  
  NOTE: Since the initial publication of this exercise in 1991, several attempts were made to solve Algorithm 2 as described above. Some attempts were very successful and obviously correct, but unfortunately many algorithms found on the Internet today (such as the recent article by Dr. James McCaffrey) mistakenly represent the nth permutation initially as a very limited integer parameter. These algorithms clearly fail for a large n within permutation sets where the length of the linear list or target exceeds 12 elements.
  
  Accepted solutions to this exercise manually set the Base-N-Odometer then calculate the nth permutation solely based upon the new Base-N-Odometer reading. Utilize the same parameter concept as found in common Factorial functions to set the Base-N-Odometer without calculating a large factorial number(s) as a result. Research the QuickPerm Reversal Algorithm (formally Example 03) and answer Permutation Exercise 9 (above) before attempting to solve this exercise.

22. Create an improved random number generator called RandPerm using the MetaPerm algorithm and a large Cyclic Redundancy Check (CRC) number. Initially populate the target array a[N] using several well known random number series then compute a large CRC number using the entire target array. Return the large CRC number as a decimal number and SWAP the elements in the target array referenced by the MetaPerm algorithm. Call the MetaPerm public function next() and repeat this process until no user request remains. (Avoid using a standard random number generator based upon "time" to populate the target array or even supplement the random CRC number returned to the user.)
    
    
    Answer the following exercises based upon the RandPerm algorithm described above:
    

• Describe the influence of N's size when N < 12 and when N >= 12.
  
  
• Calculate a CRC number from an opposite direction. Compare the outcome to the previous method implemented and report noticeable correlations (or patterns).
  
  
• Using the MetaPerm class' public variables j, i, q, and r, alternate swapping elements between the head and the tail of the target array a[N]. Measure the statistical significance (or describe the duplicate sets produced). How would your measurements change by using two or more targets initially?
  
  
• Create a permutation algorithm that cycles or thrashes a new target array and compare it to the RandPerm algorithm developed above. (Hint: Individually increment the Base N Odometer's digits cyclically or increment the odometer by a number greater than one.)
  
  
• Describe the benefits (pros and cons) of using a permutation based random number generator instead of using a common random number generator based upon time. Consider several lottery number machines that can automatically pick a number sequence for the customer. Imagine some of these machines are based upon a permutation whereas others are based upon time. What happens when a several customers purchase a ticket at the exact "machine" time? What if there was a single primary index controller array (or just one base N odometer) that was shared for all permutation based machines? A large casino can also utilize a Base N Odometer(s), instead of random events based on time, to control large payouts without loosing the appearance of randomness or luck...
  
  
• Write an essay accurately describing the vital significance of a permutation based random number generator within Artificial Intelligent programs. (HINT: What's the computer doing when it's not trying to solve a problem?)
  
  
• Can you guess my "lucky" number? (Click here for the answer.)
  
  

23. Create a computer algorithm that compares a working graphic base N odometer p[N] with a permutable target a[N] of corresponding index values. In addition, this algorithm will simultaneously display both counting processes mentioned earlier using a single integer array for the base N odometer and using two integer arrays for the respective permutable targets. Pause before each swap for at least 3 seconds and highlight the elements that were swapped within the target arrays. Label the upper index pointers then highlight the corresponding lower index odometer digits/wheels referenced.
    
    For each counting process, exactly describe the correlation between the odometer digits and the actual index order displayed. Also, compute the total number of elements swapped based only upon the base N odometer. For extra credit, accurately identify odometer settings (digit-by-digit) that directly correspond to a prime number THEN write a Prime Number Generator algorithm (called QuickPrime) by properly setting the Base N Odometer and returning a large prime decimal number from the new odometer reading. (Hint: At the outset, identify prime numbers within a large sequential list of Base N Odometer readings by counting obvious digit repetitions...)
    

24. The performance of Example_03 head reversals and the performance of Example_04 tail reversals can be drastically improved by combining the two nested loops into linear conditional statements as described in the counting QuickPerm algorithm. Combine the two nested loops within these examples, verify the output, then compare various execution times with the five examples presented on this site. In addition, the lower index variable j is replaceable by the value stored in p[i] when the upper index variable i is odd, otherwise the lower index variable j is replaceable by the value stored in p[0]. Prove all optimizations that are universal.
    

25. Drastically improve the performance of the Steinhaus-Johnson-Trotter Algorithm (or the SJT Algorithm) by incorporating a Base-N-Odometer. Specifically utilizing the Base-N-Odometer model create (then compare) three algorithms to produce the following permutation sets: The first algorithm will produce a set in lexicographical order (index sorting), the second algorithm will produce a set by transposing adjacent elements (Steinhaus-Johnson-Trotter Algorithm), and the third algorithm will produce a set based upon the output from Albert Nijenhuis' & Herbert S. Wilf's Combinatorial Algorithm(s). Also, NO recursion allowed. (Hint: In addition to formally defining index variables, the Base-N-Odometer must also control the overall iteration process for any large cyclic-permutation. For more information review Example-03.)
    

26. Add a private function to MetaPerm that returns the largest permutation subset completed in t seconds. Integrate this function in order to dynamically manage time, to distribute reasonable jobs, and to solve complex problems such as a large tour for the traveling salesman (TSP).
    

27. Calculate the number of tasks your personal computer can complete within ten (10) seconds, then utilize Example-03 for multitasking within a similar timeframe. Present all findings in a formal report. (Hint: Confine all tasks within a ten-second Base N Odometer range ... a queue of queues.)
    

28. Permutation exercise 7 combined head and tail QuickPerm algorithms, but ignored the four indices returned by the Meta-Permutation Class. Incorporate a single MetaPerm object to answer permutation exercise 7 as written above. In addition, consider the following exchanges upon the target array(s): SWAP(a[i], a[q]), SWAP(a[i], a[r]), SWAP(a[j], a[q]), and SWAP(a[j], a[r]). Accurately describe an index adjustment when two indices are equivalent. Again, measure statistical significance using a single target a[] and determine when to halt execution. Be creative and attempt to combine this additional assignment with previous QuickPerm examples in any combination. How would your argument change by using two or more duplicate targets initially? Present all findings in a formal report. (Hint: Generally after progressive research utilizing various forms of the QuickPerm algorithm, numerous innovative generation sequences are discovered...)
    

29. Remote controlled locks are extremely vulnerable to electronic eavesdropping devices and consequently devious playback tactics. Precisely describe a method of implementing two auto-synchronized Base N Odometers broadcasting dynamic encoded signals. (Hint: Increment or decrement the Base N Odometers by a number greater than one and allow the odometers to freely rollover...)
    

30. Formally prove both countdown QuickPerm reversal algorithms as presented on this website. Reports shall begin with a broad empirical proof followed by a sound analytical proof. How can a QuickPerm Reversal Algorithm be used to omit duplicate generations within a complete permutation set? (HINT: Compare the QuickPerm Reversal Algorithm to a single-pass Palindrome detection algorithm.)
    

31. Modify the counting Meta-Permutation Class presented in exercise 19 by adding four index variables described as follows: define two indices in the MetaPerm constructor for head and tail reversals then declare two additional indices to accurately represent a countdown process. Again all indices are private. Finally, incorporate additional index variables in order to transpose adjacent elements within the target data structures (reference the Steinhaus-Johnson-Trotter Algorithm). For extra credit, create a universal Meta-Permutation Class that provides unique indices for all known generation sequences. (Hint: Fundamentally any generation sequence is possible utilizing the Base N Odometer model. In this case, the Base N Odometer must control the overall iteration process for a large cyclic-permutation. For more information review permutation exercise 25 above and the notes for Example-03.)
    

32. A universal MetaPerm algorithm is capable of calculating and returning various indices for any generation sequence regardless of the target data structure(s) at hand. Accurately describe the correlation of the indices returned and common data structures such as linked-lists, perfect multi-dimensional arrays, tree structures, a queue of queues, and graphs. Provide an operational algorithm and practical examples for each data structure referenced.

33. The QuickPerm Reversal Algorithms presented on this website are well suited to detect Palindrome substrings within a target array(s). Modify a QuickPerm Reversal Algorithm to omit possible duplicate generations within a complete permutation set. To accomplish this goal, a stated guideline is compromised: The linear permutable target can NOT be examined.

34. Utilize the Base N Odometer model to create a very efficient "Big Integer Calculator". No Stacks Allowed!

35. Write an intelligent permutation algorithm to solve any given "Rubik's Cube". Obey the rules of Rubik's Cube (3 x 3 x 3 or 5 x 5 x 5) for rotations and swapping colored cubes. (Hint: Examine each side of the cube before applying a focused permutation. Repeat this process for the remaining sides until a solution is reached.)

36. Use the QuickPerm or the MetaPerm algorithms presented on this web site to solve the puzzle Spinout, manufactured by Binary Arts Corporation. (Hint: Utilize the Base-N-Odometer model.)

37. Focused permutation efforts, such as the QuickPerm and the MetaPerm algorithms, clearly offer many efficient timesaving advantages. Compare and contrast the QuickPerm and the MetaPerm algorithms to common cyclic permutation algorithms, complex heuristic models, and uncontrollable recursive solutions.

38. Examination of very large arrays or continuous linear character streams of an unknown length is not feasible utilizing cyclic permutation algorithms or even heuristic approaches. Considering the QuickPerm and the MetaPerm algorithms presented on this web site, discuss a procedure for processing a continuous linear character stream(s).

39. Discuss the disadvantages of implementing a "Random Permutation". In addition, describe a "Miracle Method" and the relationship to a "Random Permutation" for very large target lists.

40. Solve the Traveling Salesman Problem for an unknown number of cities. Assume the city coordinates are ordered in the linear stream according to the distance ascending from the salesman's home city (the starting point). (Hints: Expand your view by implementing mathematic annealing processes upon several centralized city coordinates. Overall, approximate a time period to complete this task.)

41. Text encryption algorithms, including MIME, produce simple printable ASCII characters that can be transmitted within the body of an email message. Utilize a common MIME encryption algorithm to produce a simple text file, THEN feed the output stream into the QuickPerm algorithm. Allow the user to enter a Personal Identification Number (or PIN) that advances the Base-N-Odometer for each character stuffed into the target array. Overflow from the target array is returned as output. (HINT: Initialize the target array to NULL, then choose a consistent entry point to stuff the array. Keep the size of the target array less than fifteen and allow the corresponding parallel Base-N-Odometer to freely rollover.)

42. The Permutation Clock can also be described as a clock's pendulum. Compose a five-page essay with several illustrations to accurately describe a pendulum analogy and perpetual improvements within any computer application over time.

43. Write a computer program to simultaneously display (graphically) a Permutation Clock and a Pendulum along with a scrolling Permutation Ruler.