16 August 2013

Algorithmathon

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
``````require 'spec_helper'

shared_examples "a permutation" do | target_string, target_method, goal |

describe "When #{target_method}' is called" do
before(:each) do
@string = AlgorithmString.new(target_string)
end

it "should not return nil" do
@string.send(target_method).should_not be_nil
end

it "should return #{goal}" do
@string.send(target_method).length.should == goal
end

it "should return #{goal} when 'iteration_count' is called" do
@string.send(target_method)
@string.iteration_count.should == goal
end

it "should match @verify_array" do
verify_array = target_string.chars.to_a.permutation.map(&:join)
local_array = @string.send(target_method)
verify_array.each { | value |
local_array.include?(value).should be_true
}
end
end
end

describe AlgorithmString do

describe "Class" do
it "should have method 'permutate'" do
AlgorithmString.method_defined?(:permutate).should be_true
end

it "should have method 'permutate2'" do
AlgorithmString.method_defined?(:permutate2).should be_true
end

it "should have method 'permutate3'" do
AlgorithmString.method_defined?(:permutate3).should be_true
end

it "should have method 'iteration_count'" do
AlgorithmString.method_defined?(:iteration_count).should be_true
end
end

describe "Instance" do

describe "'ABC' permutations" do
it_should_behave_like "a permutation", "ABC","permutate", 6
it_should_behave_like "a permutation", "ABC","permutate2", 6
it_should_behave_like "a permutation", "ABC","permutate3", 6

end
describe "'ABCD' permutations" do
it_should_behave_like "a permutation", "ABCD","permutate", 24
it_should_behave_like "a permutation", "ABCD","permutate2", 24
it_should_behave_like "a permutation", "ABCD","permutate3", 24

end
describe "'ABCDE' permutations" do
it_should_behave_like "a permutation", "ABCDE","permutate", 120
it_should_behave_like "a permutation", "ABCDE","permutate2", 120
it_should_behave_like "a permutation", "ABCDE","permutate3", 120

end
end
end``````

Our code to meet these tests.

algorithm_string.rb
``````class AlgorithmString < String

#Determine all possible orderings of characters in a string
#
#  - returns an array with all the possible orderings.
def permutate()
@iteration_count=0
return_array = Array.new()
permutate_by_recursion(return_array,Array.new(),Array.new(),0)
return_array
end

def permutate2()
@iteration_count=0
return_array = Array.new()
string_array = self.split('')
permutate_by_recursion2(return_array,string_array,0)
return_array
end

def permutate3()
@iteration_count=0
return_array = Array.new()
string_array = self.split('')
permutate_by_recursion3(return_array,string_array,"")
return_array
end

private
def permutate_by_recursion(return_array,build_array,tracking_array, current_position)
final_position= self.length - 1

if current_position > final_position
return_array[return_array.length]=build_array.join()
return
end

for i in 0..final_position
@iteration_count = @iteration_count + 1
unless tracking_array[i]
build_array.push(self[i])
tracking_array[i]=true
permutate_by_recursion(return_array,build_array,tracking_array,current_position + 1)
build_array.pop()
tracking_array[i]=false
end
end
end

def permutate_by_recursion2(return_array, string_array, current_position)
final_position= self.length - 1

if current_position > final_position
return_array[return_array.length]=string_array.join()
return
end

for i in current_position..final_position
@iteration_count = @iteration_count + 1
switch_character(string_array,current_position,i)
permutate_by_recursion2(return_array,string_array,current_position + 1)
switch_character(string_array,current_position,i)
end
end

def switch_character(string_array,first,second)
value_holder=string_array[second]
string_array[second]=string_array[first]
string_array[first]=value_holder
end

def permutate_by_recursion3(return_array, string_array, string_value)
if string_array.length == 1
return_array[return_array.length]=string_value + string_array
return
end
string_array.each_with_index { | value, index |
@iteration_count = @iteration_count + 1
prefix = string_value + value
temp_array = string_array.clone()
temp_array.delete_at(index)
permutate_by_recursion3(return_array, temp_array, prefix)
}

end

end``````

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.

Less Is More ~ Older posts are available in the archive.