Capitalization Permutations

Question

I wanted to write a snippet of ruby that would take a string and output all possible permutations of capitalizations. Basically, I have a password that I remember, but I don't remember how it is capitalized.

I have the following so far:

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

This works well enough, but I was wondering if any rubyists out there could help me refine it so that it doesn't have to work needlessly on strings with numbers.

For example, the string "tst1" generates:

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

The output I'm looking for is:

tst1
tsT1
tSt1
tST1
Tst1
TsT1
TSt1
TST1

Any ideas?

Answer 1

What a great opportunity to put my classes of "Derivation of algorithms", the Dijkstra method, back from the days of University into practice here. This is the 'clean' version

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

EDIT: Dijkstra taught us not to optimize prematurely, so I figured the Array-version would better be added separately :-) :

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

And to make it blazing fast one converts into tail recursion, with the help of an extra method argument:

# 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

Now this is actually very slow, but tail recursion allows for a simple re-write (see for yourself) into the optimized version:

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 

How much does this matter? Well let's run some timed tests, for the fun of it:

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

On my machine this shows the difference:

tail: 0.982241
normal: 0.285104
superfast: 0.168895

The speed increase and performance benefits become visible from non-trivial strings; "tst1" will run fast in the clean version. Hence, Dijkstra was right: no need to optimize. Though it was just fun to do it anyway.

Answer 2

try john the ripper, or cain and able, or any password cracking software

Answer 3

You should make another array and instead of put just include them into the array if it isn't already included in the array. Then after your loop, join them with a \n or whatever you like.

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

The Output:

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