From: tamouse mailing lists <tamouse.lists@...>
Date: 2013-04-13T23:17:16+09:00
Subject: Re: Looking for a more elegant solution.

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.