Combinatorics

[Peter Dobcsanyi]

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.

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

Try to compare the running times of comb() and combo() with some really
"large" (depending on your machine) numbers.

perm() can be changed similarly.

    Peter