gpt4 book ai didi

ruby - 大写排列

转载 作者:数据小太阳 更新时间:2023-10-29 06:52:16 27 4
gpt4 key购买 nike

我想编写一个 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

这工作得很好,但我想知道是否有任何 ruby​​ists 可以帮助我改进它,这样它就不必在带有数字的字符串上不必要地工作。

例如,字符串“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

有什么想法吗?

最佳答案

这是一个很好的机会,可以在这里实践我大学时代的“算法推导”类(class)和 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 是对的:不需要优化。尽管这样做很有趣。

关于ruby - 大写排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1390147/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com