将我的“算法推导”课程（Dijkstra 方法）从大学时代回到这里付诸实践，真是一个绝佳的机会。这是“干净”的版本
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
编辑：Dijkstra 教我们不要过早优化，所以我认为最好单独添加 Array-version :-)：
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”将在干净版本中快速运行。因此，Dijkstra 是对的：不需要优化。虽然这样做很有趣。