Home Original page

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