Combinatorics
Alex Martelli
aleax at aleax.it
Thu Oct 10 06:00:38 EDT 2002
Peter Dobcsanyi wrote:
> Thorsten Kampe <thorsten at thorstenkampe.de> wrote:
>> The program uses some standard external routines:
>> comb, fact, perm, quotient_set, set and cartes listed beneath the code
> ...
>> #v+
>> def comb(n, k):
>> return fact(n) / (fact(k) * fact(n-k))
>>
>> def fact(integer):
>> factorial = 1
>> for factor in range(2, integer+1):
>> factorial *= factor
>> return factorial
>>
>> def perm(n, k):
>> return fact(n) / fact(n-k)
>
> Risking the sin of premature optimization :-), here is a version for
> comb() not defined in terms of the factorial function.
I think a simpler optimization is to memoize fact (untested, I'm
just typing this in by memory):
_facts = [1]
def fact(integer):
assert integer >= 0
for i in range(len(_facts), integer+1):
_facts.append(i*_facts[-1])
return _facts[integer]
This makes it fast enough in an amortized sense to use freely
as a primitive. And you only need to pre-populate _facts in
the obvious way to a greater extent to reduce the startup
cost to be amortized.
You need _facts = [1L] if you want to support old versions
of Python, of course.
Alex
More information about the Python-list
mailing list