大写排列

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

这工作得很好，但我想知道是否有任何红宝石专家可以帮助我改进它，这样它就不必在带有数字的字符串上不必要地工作。

例如，字符串“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 教我们不要过早优化，所以我认为数组版本最好单独添加:-) :

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 是对的：不需要优化。但无论如何，这样做很有趣。

Answer 2

尝试 john the ripper、cain andable 或任何密码破解软件

Answer 3

您应该创建另一个数组，而不是 put，如果数组尚未包含它们，则只需将它们包含到数组中。然后在循环之后，用 \n 或您喜欢的任何内容将它们连接起来。

def permute(str)

  perms = Array.new
  correct = []
  (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

    correct << str_arr.to_s unless correct.include?(str_arr.to_s)
  end

  puts correct.join("\n")
end

输出：

>> permute("tst1")
tst1
tsT1
tSt1
tST1
Tst1
TsT1
TSt1
TST1

Answer 4

还有另一种解决方案（谁能抗拒尝试呢？）：

require 'pp'
class String
  def permute
    return [self, self.upcase].uniq if size <= 1
    [self[0..0], self[0..0].upcase].uniq.map do |x|
      self[1..-1].permute.map {|y| x+y}
    end.flatten
  end
end
pp 'tst1'.permute

return ["tst1", "tsT1", "tSt1", "tST1", "Tst1", "TsT1", "TSt1", "TST1"]

Answer 5

好吧，我不了解 ruby​​，所以我可能是错的，但在我看来，代码是有效的。只是因为您在进行大小写排列时没有考虑数字。数字一只有一个版本，因此大小写看起来相同。因此：“tst1”和“tst1”，“tsT1”和“tsT1”等等。

您是否尝试过使用“acb”的代码？这工作正常还是你遇到同样的问题？

Answer 6

一种简单的方法可能是从字符串中删除数字，将结果传递给您已经编写的函数，然后将数字放回到同一索引处。

Answer 7

也许不是最优雅的解决方案，但您可以更改

puts str_arr.to_s

为

passwords << str_arr.to_s

循环后

puts passwords.uniq

Answer 8

对原始程序进行轻微修改

#!/usr/local/bin/ruby
$result = []
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
    $result << str_arr.to_s
  end
  $result
end
puts permute(ARGV[0]).uniq

Answer 9

像这样？

def perm(s)
  s2 = s.upcase
  n = s.size
  ary = [s.split(//), s2.split(//), (0..(n-1)).map{|i| 2**i}.reverse].transpose
  (0..(2**n-1)).map{|i| ary.map{|a, b, c| ((c & i) > 0) ? b : a }.join }.uniq
end

p perm('tst1')
# ["tst1", "tsT1", "tSt1", "tST1", "Tst1", "TsT1", "TSt1", "TST1"]