Looking for a more elegant solution

ruby-talk
1

I'm new to ruby and working on such a problem:

There n numbered letters and n numbered envelops. The letter x can't be
put into the envelop x. What I want is to print out all the possible
cases.

[letter(x1), letter(x2), ... , letter(xn)]
      > > >
envelop1, envelop2, ... , envelop n

The index of Array + 1 ---> the number of the envelop

The element of Array ---> the number of the letter

Input: n = 3.
Output: [1, 3, 2], [2, 3, 1]

Input: n = 4.
Output: [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2],
          [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2],
          [4, 3, 2, 1]

Here is my code:

···

-----------------------
$nums = []

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
------------------------

Sorry for my poor English. Thank you very much.

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

2

Try the following:

1.upto(n).to_a.permutation(n).to_a.delete_if do |perm|
  perm.any? { |letter| letter == perm[letter -1] }
end

Bye

···

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

3

Try the following:

1.upto(n).to_a.permutation(n).to_a.delete_if { |perm| perm.any? { |letter|
letter == perm[letter -1] } }

···

2013/4/12 Shaw xx <lists@ruby-forum.com>

I'm new to ruby and working on such a problem:

There n numbered letters and n numbered envelops. The letter x can't be
put into the envelop x. What I want is to print out all the possible
cases.

[letter(x1), letter(x2), ... , letter(xn)]
      > > >
envelop1, envelop2, ... , envelop n

The index of Array + 1 ---> the number of the envelop

The element of Array ---> the number of the letter

Input: n = 3.
Output: [1, 3, 2], [2, 3, 1]

Input: n = 4.
Output: [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2],
          [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2],
          [4, 3, 2, 1]

Here is my code:
-----------------------
$nums =

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
------------------------

Sorry for my poor English. Thank you very much.

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

4

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/.

5

Hello,

Maybe this one is a little more elegant :

def f( accu,already, n, times )
  if n > times
    accu << already.dup
  else
    ((1..times).to_a - already-[n]).each do |i|
      f( accu, already+[i], n+1, times )
    end
    accu
  end
end
p f([],[],1,4)

···

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

6

Interesting solution, Pablo!

It falls off the edge for n > 9:

       user system total real
   0.000000 0.000000 0.000000 ( 0.000015)
   0.000000 0.000000 0.000000 ( 0.000012)
   0.000000 0.000000 0.000000 ( 0.000018)
   0.000000 0.000000 0.000000 ( 0.000051)
   0.000000 0.000000 0.000000 ( 0.000227)
   0.000000 0.000000 0.000000 ( 0.001364)
   0.020000 0.000000 0.020000 ( 0.010818)
   0.190000 0.000000 0.190000 ( 0.198450)
  15.710000 0.000000 15.710000 ( 15.713011)

After 9, it goes on for far too long for me to stand! I killed it
after 20 minutes.

···

On Fri, Apr 12, 2013 at 10:39 AM, Pablo Bianciotto <bianciottopablo@gmail.com> wrote:

Try the following:

1.upto(n).to_a.permutation(n).to_a.delete_if { |perm| perm.any? { |letter|
letter == perm[letter -1] } }

2013/4/12 Shaw xx <lists@ruby-forum.com>

I'm new to ruby and working on such a problem:

There n numbered letters and n numbered envelops. The letter x can't be
put into the envelop x. What I want is to print out all the possible
cases.

[letter(x1), letter(x2), ... , letter(xn)]
      > > >
envelop1, envelop2, ... , envelop n

The index of Array + 1 ---> the number of the envelop

The element of Array ---> the number of the letter

Input: n = 3.
Output: [1, 3, 2], [2, 3, 1]

Input: n = 4.
Output: [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2],
          [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2],
          [4, 3, 2, 1]

Here is my code:
-----------------------
$nums =

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
------------------------

Sorry for my poor English. Thank you very much.

7

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/\.

8

def mails( n, times ,already=[], accu=[])
  return accu << already if n > times
  nexts=(1..times).to_a - already-[n]
  nexts.each { |i| mails( n+1, times, already+[i], accu ) }
  accu
end

p mails(1,4)

···

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

9

8 is 40,320 permutations, but 9 is 362,880!

Julian

···

On 14/04/2013, at 12:17 AM, tamouse mailing lists <tamouse.lists@gmail.com> wrote:

On Fri, Apr 12, 2013 at 10:39 AM, Pablo Bianciotto > <bianciottopablo@gmail.com> wrote:

Try the following:

1.upto(n).to_a.permutation(n).to_a.delete_if { |perm| perm.any? { |letter|
letter == perm[letter -1] } }

2013/4/12 Shaw xx <lists@ruby-forum.com>

I'm new to ruby and working on such a problem:

There n numbered letters and n numbered envelops. The letter x can't be
put into the envelop x. What I want is to print out all the possible
cases.

[letter(x1), letter(x2), ... , letter(xn)]
     > > >
envelop1, envelop2, ... , envelop n

The index of Array + 1 ---> the number of the envelop

The element of Array ---> the number of the letter

Input: n = 3.
Output: [1, 3, 2], [2, 3, 1]

Input: n = 4.
Output: [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2],
         [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2],
         [4, 3, 2, 1]

Here is my code:
-----------------------
$nums =

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
------------------------

Sorry for my poor English. Thank you very much.

Interesting solution, Pablo!

It falls off the edge for n > 9:

      user system total real
  0.000000 0.000000 0.000000 ( 0.000015)
  0.000000 0.000000 0.000000 ( 0.000012)
  0.000000 0.000000 0.000000 ( 0.000018)
  0.000000 0.000000 0.000000 ( 0.000051)
  0.000000 0.000000 0.000000 ( 0.000227)
  0.000000 0.000000 0.000000 ( 0.001364)
  0.020000 0.000000 0.020000 ( 0.010818)
  0.190000 0.000000 0.190000 ( 0.198450)
15.710000 0.000000 15.710000 ( 15.713011)

After 9, it goes on for far too long for me to stand! I killed it
after 20 minutes.

10

??

def mails( n, times ,already=[])
  return [already] if n > times
  nexts=(1..times).to_a - already-[n]
  nexts.inject([]) { |a,i| a+mails( n+1, times, already+[i] ) }
end

p mails(1,4)

···

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