The inject thing makes perfect sense when you think about it, should speed up my permute() and permutation_number() methods.
I posted a second each_permutation function that doesn't use factorials and ends up being faster than the original.
Before including it in facets, it should be changed slightly though - I don'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 starting with the end array and subtracting rather than adding. I'll send it to you 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
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:
def factorial
return 0 if zero?
f = 1
2.upto(self) { |n| f *= n }
f
end
That should help a good bit.
T.
#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################