Понадобилось мне намедне генерировать перестановки. Пошукал гуглом, почитал умные книги. В итоге, наметилось три кандидата на реализацию.

Кандидат первый:

class Array
  def perm(n = size)
    if size < n or n < 0
    elsif n == 0
      yield([])
    else
      self[1..-1].perm(n - 1) do |x|
        (0...n).each do |i|
          yield(x[0...i] + [first] + x[i..-1])
        end
      end
      self[1..-1].perm(n) do |x|
        yield(x)
      end
    end
  end
end

Кандидат второй: gem install permutation.

Кандидат третий: встроенный метод Array#permutation в Ruby 1.9.

Провел бенчмарк, результаты такие:

Ruby 1.8:

                        user     system      total        real
Array#perm            2.670000   0.070000   2.740000 (  2.828519)
Permutation           1.950000   0.090000   2.040000 (  2.157960)

Ruby 1.9:

                        user     system      total        real
Array#perm            2.150000   0.000000   2.150000 (  2.289050)
Permutation           1.280000   0.000000   1.280000 (  1.342824)
Array#permutation     0.290000   0.000000   0.290000 (  0.290440)

Код теста:

require 'rubygems'
require 'permutation'
require 'benchmark'

class Array
  def perm(n = size, &blk)
    if n == 0
      yield []
    elsif n >= 0 and n <= size
      self[1..-1].perm(n - 1) do |x|
        (0...n).each do |i|
          yield x[0...i] + [first] + x[i..-1]
        end
      end
      self[1..-1].perm(n) do |x|
        yield x
      end
    end
  end
end

n = (0..8).to_a
Benchmark.bm(20) do |x|
  x.report("Array#perm") { n.perm { |a| ;} }
  x.report("Permutation") do
    p = Permutation.new(9)
    p.map { |a| ; }
  end
  if RUBY_VERSION >= '1.9'
    x.report("Array#permutation") { n.permutation { |a| ; } }
  end
end