CODEWITHSUNDEEP
pythonlambda
Bob
Bob

Reputation: 756

Why am I getting errors using the Lambda function?

I am messing around with the lambda function and I understand what I can do with it in a simple fashion, but when I try something more advanced I am running into errors and I don't see why.

Here is what I am trying if you can tell me where I am going wrong it would be appricated.

import math

C = lambda n,k: math.factorial(n)/(math.factorial(k))(math.factorial(n-k))

print C(10,5)

I should note that I am running into errors trying to run the code on Codepad. I do not have access to Idle.

Upvotes: 2

Views: 718

Answers (3)

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

Presumably the value you wish to compute is “n-choose-k”, the number of combinations of n things taken k at a time. The formula for that is n!/(k! * (n-k)!). When the missing * is added to your calculation, it produces n!/k! * (n-k)!, which equals (n!/k!)*(n-k)!. (Note, k! evenly divides n!.) For example, with n=10 and k=5, C(10,5) should be 3628800/(120*120) = 252, but your calculation would give 3628800/120*120 = 3628800, which is incorrect by a factor of 14400.

You can of course fix the parenthesization: 

>>> C = lambda n,k: math.factorial(n)/(math.factorial(k)*math.factorial(n-k))
>>> C(10,5)
252

But note that if math.factorial(j) takes j-1 multiplications to calculate, then C(n,k) takes n-1+k-1+n-k-1+1 = 2*n-2 multiplications and one division. That's about four times as many multiply operations as necessary. The code shown below uses j multiplies and j divides, where j is the smaller of k and n-k, so j is at most n/2. On some machines division is much slower than multiplication, but on most machines j multiplies and j divides will run a lot faster than 2*n-2 multiplications and one division.

More importantly, C(n,k) is far smaller than n!. Computing via the n!/(k!*(n-k)!) formula requires more than 64-bit precision whenever n exceeds 20. For example, C(21,1) returns the value 21L. By contrast, the code below computes up to D(61,30)=232714176627630544 before requiring more than 64 bits to compute D(62,31)=465428353255261088L. (I named the function below “D” instead of “C” to avoid name clash.)

For small computations on big fast machines, the extra multiplies and extra precision requirements are unimportant. However, for big computations on small machines, they become important.

In short, the order of multiplications and divisions in D() keeps the maximum intermediate values that appear minimal. The largest values appear in the last pass of the for loop. Also note that in the for loop, i is always an exact divisor of c*j and no truncation occurs. This is a fairly standard algorithm for computing “n-choose-k”.

def D(n, k):
    c, j, k = 1, n, min(k,n-k)
    for i in range(1,k+1):
        c, j = c*j/i, j-1
    return c

Results from interpreter:

>>> D(10,5)
252
>>> D(61,30)
232714176627630544
>>> D(62,31)
465428353255261088L

Upvotes: 1

Óscar López
Óscar López

Reputation: 236004

Try this:

from math import factorial
from __future__ import division

C = lambda n, k : factorial(n) / factorial(k) * factorial(n-k)

print C(10,5)
> 3628800.0

You were missing a *, and also it's possible that the division should take in consideration decimals, so the old division operator / won't do. That's why I'm importing the new / operator, which performs decimal division.

UPDATE:

Well, after all it seems like it's Codepad's fault - it supports Python 2.5.1, and factorial was added in Python 2.6. Just implement your own factorial function and be done with it, or even better start using a real Python interpreter.

def factorial(n):
    fac = 1
    for i in xrange(1, n+1):
        fac *= i
    return fac

Upvotes: 3

Jordan Lewis
Jordan Lewis

Reputation: 17928

I think you're missing a * between the second 2 factorial clauses. You're getting an error because you're trying to run (math.factorial(k))(math.factorial(n-k)), which turns into something like 10(math.factorial(n-k), which makes no sense.

Upvotes: 1

Related Questions