Code Excursion

Algorithmathon Day 16: Permutations of a String

Created: 16 August 2013 Modified:

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
  attr_reader :iteration_count

  #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[0]
      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 n³ and n! x n². Our second solution permutate2 switches values around with the string and is able to do considerably better. It solves the problem somewhere between n² and n x n². 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