大学時代の「アルゴリズムの導出」、ダイクストラ法をここで実践する絶好の機会です。これは「クリーン」バージョンです
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
編集:ダイクストラは時期尚早に最適化しないように教えてくれたので、配列バージョンを個別に追加する方がよいと考えました:-):
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
そして、超高速にするために、追加のメソッド引数を使用して末尾再帰に変換します。
# 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
これは実際には非常に遅いですが、末尾再帰により、最適化されたバージョンに簡単に書き直すことができます (自分の目で確かめてください) 。
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
これはどのくらい重要ですか？楽しみのために、いくつかの時限テストを実行しましょう。
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
私のマシンでは、これは違いを示しています：
tail: 0.982241
normal: 0.285104
superfast: 0.168895
速度の向上とパフォーマンスの利点は、重要な文字列から明らかになります。「tst1」は、クリーン バージョンで高速に実行されます。したがって、ダイクストラは正しかった: 最適化する必要はありません。とにかくそれをするのはただ楽しかったです。