16 August 2013

## Algorithmathon Day 16: Permutations of a String

Day 16’s goal has turned out to be surprisingly fascinating. Permutations of a string have a solution that is a factor of the length of the string. This means that a string with four characters will have 24 solutions which is the result of 4 x 3 x 2 x 1. This then can be our ideal goal and is represented by n!. We want to find the permutations of a string with the number of operations being equal or close to the multiplied factors of the string length.

This goal turned out to be difficult to achieve. In fact we will see that we do not achieve it. We will explore three solutions each of which provides a somewhat improved solution to the prior one. Even so we will not reach our goal. Searching for the solution was very interesting and I only stopped because I needed to move on to other subjects.

The number of iterations is the length of the string raised to the power of the number of factors in the string. A string of length 3 has 6 permutations. Which is the factorial of 3. 3 x 2 x 1 = 6. Research suggests an answer of n! x n x n.

We should now construct our RSpec tests. This time around we will leave one test failing because we never reach our ideal goal of n! iterations.

algorithm_string_spec.rb

Our code to meet these tests.

algorithm_string.rb

As you can see the first solution permutate was not very efficient and required iterations greater than n3 and n! x n2. Our second solution permutate2 switches values around with the string and is able to do considerably better. It solves the problem somewhere between n2 and n x n2. This solutions is my favorite because it seems the least resource intensive. Finally we have permutate3 which uses the fewest iterations/recursive calls. The difference is not insignificant and the this solution could also be applied to permutate2 to reduce its number of recursive calls.

tags: Algorithm - Algorithmathon - RSpec - Ruby

Less Is More