From: Julian Leviston <julian@...>
Date: 2013-04-14T00:24:22+09:00
Subject: Re: Looking for a more elegant solution.

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