From: Pablo Bianciotto <lists@...>
Date: 2013-04-14T02:52:07+09:00
Subject: Re: Looking for more elegant solutions.

This would improve performance by removing the delete_if iteration over
the full array. But it still won't work for n > 10:

=begin

out = []
1..n).to_a.permutation do |perm|
  out << perm unless perm.any? { |letter| letter == perm[letter -1] }
end
out

=end

Do you need to have all the permutations  allocated in an array? If you
don't, maybe you should try building an enumerator to ask for the next
one each time you need one. You could also use Enumerator#lazy if you
are using ruby 2.0.

Anyway, without delete_if this approach it's almost twice as fast as
your original code.

=begin

require "benchmark"

def f( already, n, times )
  if n > times
    $nums << already.dup
    return
  else
    1.upto(times) do |i|
      next if ((already.include? i) || n == i)
      already << i
      f( already, n+1, times )
      already.pop
    end
  end
end

Benchmark.bm(15) do |x|
  (8..11).each do |n|
    x.report("new_perm N = #{ n }:") do
      out = []
      (1..n).to_a.permutation do |perm|
        out << perm unless perm.any? { |letter| letter == perm[letter
-1] }
      end
      out
    end
    x.report("original N = #{ n }:") do
      $nums = []
      f([],1,n)
      $nums
    end
    if n < 10
      x.report("old_perm N = #{ n }:") do
        1.upto(n).to_a.permutation(n).to_a.delete_if do |perm|
          perm.any? { |letter| letter == perm[letter -1] }
        end
      end
    end
  end
end

=end

                      user     system      total        real
new_perm N = 8:   0.031000   0.000000   0.031000 (  0.043003)
original N = 8:   0.078000   0.000000   0.078000 (  0.078004)
old_perm N = 8:   0.250000   0.000000   0.250000 (  0.242014)
new_perm N = 9:   0.421000   0.000000   0.421000 (  0.422024)
original N = 9:   0.795000   0.000000   0.795000 (  0.803046)
old_perm N = 9:  16.490000   0.000000  16.490000 ( 16.499944)
new_perm N = 10:  5.085000   0.015000   5.100000 (  5.076290)
original N = 10:  9.594000   0.016000   9.610000 (  9.608550)
new_perm N = 11: 66.644000   0.265000  66.909000 ( 67.106838)
original N = 11:[FATAL] failed to allocate memory

Hope it helps!
Pablo B.

-- 
Posted via http://www.ruby-forum.com/.