Понадобилось мне намедни генерировать перестановки. Пошукал гуглом, почитал умные книги. В итоге, наметилось три кандидата на реализацию.
Кандидат первый: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
