Combinatorics

[Peter Dobcsanyi]

Peter Dobcsanyi <dpeter at designtheory.org> wrote:
> Risking the sin of premature optimization :-), here is a version for
> comb() not defined in terms of the factorial function.
> 
> def combo(n, k):
>     if k < 0 or n < k :
>         return 0
>     if 2 * k > n :
>         k = n - k 
>     b = 1
>     if k > 0 :   
>         for i in xrange(k):
>             b = (b * (n - i)) / (i + 1)
>     return b
> 

Alex Martelli <aleax at aleax.it> wrote:
> 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.

I don't know which one is simpler, but for "large" numbers the memoizing
version is not a win in this case, it has a rather big memory footprint.

For example, clocking the time of comb(32000, 31000)  I got:

                 time         memory size

combo           0.02 sec      2.5 Mbyte
memoizing       0.42 sec      839 Mbyte         !!!

The time for the memoizing version was taken the second time around, so
_facts was already populated. Continuing with the populated _facts:

      n         k       combo     memoizing

    32000    16000      1.51        1.99
    15000     7500      0.35        0.42
    15000    14000      0.02        0.16
    10000     5000      0.17        0.19
    10000     9000      0.02        0.09
     5000     2500      0.04        0.04
     5000     4500      0.01        0.02
     1000      500      0.0         0.0

 Peter