资本化排列

Question

我想编写一个ruby片段,它将获取一个字符串并输出所有可能的大写排列.基本上,我有一个我记得的密码,但我不记得它是如何大写的.

到目前为止,我有以下内容:

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

这很好用,但我想知道是否有任何rubyists可以帮助我改进它,这样它就不必在数字字符串上不必要地工作.

例如,字符串"tst1"生成:

tst1
tst1
tsT1
tsT1
tSt1
tSt1
tST1
tST1
Tst1
Tst1
TsT1
TsT1
TSt1
TSt1
TST1
TST1

我正在寻找的输出是:

tst1
tsT1
tSt1
tST1
Tst1
TsT1
TSt1
TST1

有任何想法吗？

Answer 1

这是一个很好的机会,让我的"算法推导",即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是对的:无需优化.尽管如此,它仍然很有趣.