Capitalization Permutations

capitalization, permutation, ruby

Solution

What a great opportunity to put my classes of "Derivation of algorithms", the Dijkstra method, back from the days of University into practice here. This is the 'clean' version

require 'set'

def generate_perms(str)
  if str.length == 1
    return Set.new([str.downcase, str.upcase])
  else 
    head = str[0..0]
    tail = str[1..-1]
    perms_sub = generate_perms(tail)
    d = Set.new(perms_sub.collect{|p| head.downcase + p})
    u = Set.new(perms_sub.collect{|p| head.upcase + p})
    return d | u 
  end  
end

EDIT: Dijkstra taught us not to optimize prematurely, so I figured the Array-version would better be added separately :-) :

def perms(str)
  if str.length == 1
    return Array.new([str.downcase, str.upcase])
  else 
    head = str[0..0]
    tail = str[1..-1]
    perms_sub = perms(tail)
    d = perms_sub.collect{|p| head.downcase + p}
    u = perms_sub.collect{|p| head.upcase + p}
    return (d +  u).uniq 
  end  
end

And to make it blazing fast one converts into tail recursion, with the help of an extra method argument:

# tail recursion version, no stack-overflows :-) 
def perms_tail(str, perms)
  if str.length == 1
    return perms.collect{|p| [p + str.upcase, p+ str.downcase]}.flatten.uniq
  else
    tail = perms.collect{|p| [p + str[0..0].upcase, p+ str[0..0].downcase]}.flatten
    perms_tail(str[1..-1], tail)
  end

end

begin
  perms_tail("tst1",[""]).each{|p| puts p}
end

Now this is actually very slow, but tail recursion allows for a simple re-write (see for yourself) into the optimized version:

def perms_fast_tail(str)
  perms = [""]
  tail = str.downcase
  while tail.length > 0 do
    head, tail, psize = tail[0..0], tail[1..-1], perms.size
    hu = head.upcase
    for i in (0...psize)
      tp = perms[i] 
      perms[i] = tp + hu
      if hu != head
        perms.push(tp + head)
      end  
    end  
  end
  perms
end

How much does this matter? Well let's run some timed tests, for the fun of it:

begin
  str = "Thequickbrownfox"
  start = Time.now
  perms_tail(str,[""])
  puts "tail: #{Time.now - start}"

  start2 = Time.now
  perms(str)
  puts "normal: #{Time.now - start2}"

  start3 = Time.now
  perms_fast_tail(str)
  puts "superfast: #{Time.now - start3}"
end

On my machine this shows the difference:

tail: 0.982241
normal: 0.285104
superfast: 0.168895

The speed increase and performance benefits become visible from non-trivial strings; "tst1" will run fast in the clean version. Hence, Dijkstra was right: no need to optimize. Though it was just fun to do it anyway.

Problem

I wanted to write a snippet of ruby that would take a string and output all possible permutations of capitalizations. Basically, I have a password that I remember, but I don't remember how it is capitalized. I have the following so far: ``` def permute(str) perms = Array.new (2 ** str.size).times { perms << str } perms.each_index do |i| binary = i.to_s(2) str_arr = perms[i].split(//) bin_arr = binary.split(//) while ( bin_arr.size < str_arr.size ) bin_arr.unshift('0') end bin_arr.each_index do |b| str_arr[b].upcase! if bin_arr[b] == '1' end puts str_arr.to_s end end ``` This works well enough, but I was wondering if any rubyists out there could help me refine it so that it doesn't have to work needlessly on strings with numbers. For example, the string "tst1" generates: ``` tst1 tst1 tsT1 tsT1 tSt1 tSt1 tST1 tST1 Tst1 Tst1 TsT1 TsT1 TSt1 TSt1 TST1 TST1 ``` The output I'm looking for is: ``` tst1 tsT1 tSt1 tST1 Tst1 TsT1 TSt1 TST1 ``` Any ideas?

Original source