From: tamouse mailing lists <tamouse.lists@...>
Date: 2013-04-14T04:17:56+09:00
Subject: Re: Looking for more elegant solutions.

Hi, Pablo -- I wasn't the OP, I was just wondered about limits.

On Sat, Apr 13, 2013 at 12:52 PM, Pablo Bianciotto <lists@ruby-forum.com> wrote:
> 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/.
>