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 ------------------------ I'm looking for more elegant solutions. Sorry for my poor English. Thank you very much.

on 2013-04-12 17:03

on 2013-04-12 17:34

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

on 2013-04-12 17:40

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>

on 2013-04-13 16:17

On Fri, Apr 12, 2013 at 10:39 AM, Pablo Bianciotto <bianciottopablo@gmail.com> 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.

on 2013-04-13 17:24

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

on 2013-04-13 19:52

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.

on 2013-04-13 21:18

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

on 2013-04-14 21:57

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)

on 2013-04-15 00:24

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)

on 2013-04-15 00:41

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