# Looking for more elegant solutions

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]

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

I’m looking for more elegant solutions. Sorry for my poor English. Thank
you very much.

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

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 [email protected]

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

Julian

On Fri, Apr 12, 2013 at 10:39 AM, Pablo Bianciotto
[email protected] wrote:

There n numbered letters and n numbered envelops. The letter x can’t be

## \$nums = [] 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.

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

=begin

require “benchmark”

def f( already, n, times )
if n > times
return
else
1.upto(times) do |i|
next if ((already.include? i) || n == i)
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.

Hello,

Maybe this one is a little more elegant :

def f( accu,already, n, times )
if n > times
else
f( accu, already+[i], n+1, times )
end
accu
end
end
p f([],[],1,4)

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

p mails(1,4)

Hi, Pablo – I wasn’t the OP, I was just wondered about limits.

??