From: Daniel Sheppard <daniels@...>
Date: 2005-11-06T09:04:02+09:00
Subject: Re: Fun with Permutations

------_=_NextPart_001_01C5E265.2BABE6EC
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

The inject thing makes perfect sense when you think about it, should spee=
d up my permute() and permutation_number() methods.

I posted a second each_permutation function that doesn't use factorials a=
nd ends up being faster than the original.

Before including it in facets, it should be changed slightly though - I d=
on't like the order of the permutations that come out.

For [0,1,2,3], the first permutation is [3,2,1,0] - the first should be [=
0,1,2,3], followed by [0,1,3,2] - but that's easy enough to fix by starti=
ng with the end array and subtracting rather than adding. I'll send it to=
=20you on monday, when I'm not stuck using webmail.


-----Original Message-----
From: Trans [mailto:transfire@gmail.com]
Sent: Sun 6/11/2005 4:07 AM
To: ruby-talk ML
Subject: Re: Fun with Permutations
=20
Sorry it took me some time to get to this. I've been quite busy. This
is very interesting and I'll see that it gets into Facets. I think the
trade off is worth it too. But even better I think it can be improved.

I recently got an interesting email (that I've also been meaning to get
to) on the efficency of factorial algorithms, Malte Milatz
<malte.milatz@gmx.net> wrote:

On a German Ruby board, we've been discussing about the best way to
compute the factorial of a number. While I don't suppose you to
understand German, it would be nice if you had a look at the code and
the benchmarks at <http://www.rubyforen.de/ptopic,6946.html>.

The result of our research seems to be that using inject is a highly
inefficient way in this case because the block for Enumerable#inject
takes two arguments. This may be a good reason to revise the method
found in 'facet/integer/fact'.

Note that we discarded the nil assignments seen in the first post, for
they didn't really improve things. In addition murphy changed the
benchmark to compute only up to 12! because tests on higher factorials
will be likely to be only tests on Bignum arithmetics.

;;

So in your formuation I see an inject with factorial in it. Perhaps a
little coding challenge to speed it up. And I've just added the new
factorial code to facets:

=20 def factorial
=20   return 0 if zero?
=20   f =3D 1
=20   2.upto(self) { |n| f *=3D n }
=20   f
=20 end

That should help a good bit.

T.






#########################################################################=
############
This email has been scanned by MailMarshal, an email content filter.
#########################################################################=
############

------_=_NextPart_001_01C5E265.2BABE6EC--