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, 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.