Ruby China

算法 用 Ruby 完成了同事的一个算法问题

qingxp9 · 2015年09月11日 · 最后由 love93hate 回复于 2018年08月27日 · 8304 次阅读

在写一个爆破密码的字典生成工具，其中有这样一个需求： 输入一个单词：列出这个单词的所有大小写组合，比如 ruby Ruby rUby ruBy rubY RuBy RuBY ....等等，这样 2^n 个

我想了想，思路为用二维数组保存每个字母的大写和小写：t=[["A", "a"], ["B", "b"], ["C", "c"]]， 然后对它们进行位置固定的组合，使用了数组的 product 方法：

s="abcde"
t= Array.new(s.length) { Array.new(2) }

#生成二维数组
for i in 0...(s.length)
  #处理数字
  if s[i].to_i.to_s == s[i]
    t[i][0]=s[i]
  else
    t[i][0]=s[i].upcase
    t[i][1]=s[i].downcase
  end
end

q=t[0].product
for i in 1...s.length
  q=q.product(t[i])
end

q.each do |g|
  puts g.join
end

不过我觉得写得有点丑，肯定有更优美的实现， 还望指点

msg7086 #1 2015年09月11日 
require 'pp'

def all_combi str
  combi = ['']
  # Split into upper and lower cases
  chars = str.each_char.map { |c| c =~ /[[:alpha:]]/ ? [c.upcase, c.downcase] : [c]}
  # Combine them
  chars.each do |chs|
    combi = combi.flat_map do |s|
      chs.map { |ch| s + ch }
    end
  end
  combi
end

combi = all_combi 'ru123by!'
pp combi
puts combi == combi.uniq

随便写了一下，具体效率怎么样就不知道了。

2 个赞
msg7086 #2 2015年09月11日

写 Ruby 就要用 Ruby 的思路去设计算法。 比如你这里

for i in 1...s.length
  q=q.product(t[i])
end

就至少应该写成

(1..s.size).each do |i|

或者是

t[1..-1].each do |ti|

以及

q.each do |g|
  puts g.join
end

应该写成

result = q.map(&:join)
puts result
msg7086 #3 2015年09月11日 
def all_combi_origin str
  combi = ['']
  # Split into upper and lower cases
  chars = str.each_char.map { |c| c =~ /[[:alpha:]]/ ? [c.upcase, c.downcase] : [c]}
  # Combine them
  chars.each do |chs|
    combi = combi.product(chs)
  end
  combi.map(&:join)
end

这是把你的思路用 Ruby 改写后的代码。

测速

Benchmark.bm(20) do |x|
  x.report('all_combi')        { 50_000.times { all_combi 'ru123by!' } }
  x.report('all_combi_origin') { 50_000.times { all_combi_origin 'ru123by!' } }
  x.report('all_combi_4楼')    { 50_000.times { all_combi_4楼 'ru123by!' } }
end

#                           user     system      total        real
#all_combi              1.540000   0.000000   1.540000 (  1.587790)
#all_combi_origin       2.780000   0.010000   2.790000 (  2.894336)
#all_combi_4楼          1.400000   0.000000   1.400000 (  1.443631)
4 个赞
lolychee #4 2015年09月11日 
password = "abc123"

first, *rest = password.each_char.map do |char|
  if char =~ /[[:alpha:]]/
    [char.downcase, char.upcase]
  else
    [char]
  end
end

result = first.product(*rest).map(&:join)

思路和你是一样的，判断字母那个表达式是从楼上拿的。

4 个赞
qingxp9 #6 2015年09月11日

@msg7086 @lolychee @hemslo
大涨见识，谢谢各位的指点

msg7086 #7 2015年09月11日

#5 楼 @hemslo :doge: 太下流了

douxiance #9 2015年09月11日

学习了...

love93hate #12 2018年08月27日

机器学习交易——如何使用回归预测股票价格？最近翻译了一篇文章，本人对机器学习应用在量化投资上很感兴趣，希望可以和社区大神一起交流学习。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号