Permuting Strings and Other Data

Overview

Traditional Permutations Using Recursion

Alternate Permutation Algorithm

The following algorithm does not use recursion. Instead, it uses a manual stack and a loop to permute Strings. (It can easily be modified to permute other data types.) Like the recursive algorthims shown above, the overall length of code is surprisingly short. The algorithm is much easier to understand than its recursive counterparts. The marker character mentioned in the algorithm is any character that is guaranteed not to be in the original data set. It is recommended that you use a "/" character as the marker when implementing this algorithm.

Algorithm Description:

1. create a stack

2. append a marker character to the target string and push result into the stack

3. while the stack is not empty do:

   1. pop the next string off the stack and save it in a temp variable

   2. if temp starts with marker character, remove marker and save it in a set as part of the solution. then continue while loop.

   3. if temp does not start with marker character, do a for loop:

      1. move each character before the marker to the end of the string.

      2. save in a new variable called item. (do not disturb temp)

      3. push item into the stack

4. print solution set