I've been programming for a while but for some reason figuring this out was really hard - it took me 2 and a half hours. Unsurprisingly, the solution is extremely simple...

   1  
   2  #!/usr/bin/ruby
   3  # permute - takes a word and returns all the permutations of the letters in the word
   4  
   5  def permute(word="")
   6    permutations_among(word.split(//))
   7  end
   8  def permutations_among(letters)
   9    permutations = []
  10    if letters.size == 1
  11      permutations << letters.first
  12    else
  13      letters.each_with_index do |letter, i|
  14        surrounding_letters = letters.dup; surrounding_letters.delete_at(i)
  15        permutations += permutations_among(surrounding_letters).map {|permutation| letter + permutation }
  16      end
  17    end
  18    permutations
  19  end
  20  
  21  permute(ARGV.shift).each {|permutation| puts permutation }

Some benchmarks against other implementations:

* Array#permutations: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844
* Array#perm: http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb
* geta: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
* String#perm (based on geta)
* Array#each_permutation: http://knanshon.blogspot.com/2006/08/ruby-permutations.html
* permutation: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/140345

                                              user     system      total        real
permutations_among:                       1.680000   0.010000   1.690000 (  1.700779)
Array#permutations:                       1.740000   0.010000   1.750000 (  1.798288)
geta:                                     2.430000   0.010000   2.440000 (  2.506668)
String#perm:                              2.260000   0.010000   2.270000 (  2.280652)
Array#each_permutation:                   0.820000   0.000000   0.820000 (  0.827463)
permutation:                              2.140000   0.010000   2.150000 (  2.171966)

Benchmark code:

   1  
   2  require 'benchmark'
   3  
   4  N = 1_000
   5  Benchmark.bm(40) do |x|
   6    letters = %w(a b c d e)
   7    string = "abcde"
   8    x.report("permutations_among:") do
   9      N.times { permutations_among(letters) }
  10    end
  11    x.report('Array#permutations:') do
  12      N.times { letters.permutations }
  13    end
  14    x.report('geta:') do
  15      N.times { geta(string) }
  16    end
  17    x.report('String#perm:') do
  18      N.times { string.perm }
  19    end
  20    x.report('Array#each_permutation:') do
  21      N.times { letters.each_permutation {|perm| } }
  22    end
  23    x.report('permutation:') do
  24      N.times { 0.upto(string.length.factorial-1) {|i| permutation(string, i)} }
  25    end
  26  end

So, not bad for a first try ;)