Iteration for Factorials

[Marco Mariani]

import urllib
import re
urllib.URLopener.version = "Mozilla/4.0"

def fact(x):
r = re.compile(r"%d ! = (\d+)" % x)
for line in urllib.urlopen("http://www.google.cl/search?q=%d%!" % x):
m = r.search(line)
if m:
return int(m.group(1))

You solution reminds me the web-based WTF calculator.

http://worsethanfailure.com/Articles/OMGWTF-Finalist-05-WTF-Web-Calc.aspx

 

[mensanator]

So, where is the problem?

The fact that it returns 1 for negative x?

And didn't you see my followup message? About how the
example, as posted, doesn't even produce correct answers
for legal values of x?

if not allowing negative numbers is so
important for you,

Mathematical consistency is only important to _me_?

add a if statement and raise a ValueError exception.

Not necessary when done correctly. Didn't you see my example?

 

[mensanator]

eheh, indeed.

def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1

Needs work.

IDLE 1.2 try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1
1

 

[Marco Mariani]

Needs work.

Uh... ok.. this one gives an exception ;-)


def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return n>=0 or ValueError



print fact(-1)
<type 'exceptions.ValueError'>

 

[Hendrik van Rooyen]

That's how ARM processors work, and they're everywhere these days.

Yes, worse luck. The market has chosen...

- Hendrik

 

[Nick Craig-Wood]

I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

Here is the math geek answer ;-)

import math

def factorial(i):
n = i + 1
return math.exp(-n)*(n**(n-0.5))*math.sqrt(2*math.pi)*(1. + 1./12/n + 1./288/n**2 - 139./51840/n**3)

Works for non integer factorials also...

See here for background

http://mathworld.wolfram.com/StirlingsSeries.html

 

[Lou Pecora]

Here is the math geek answer ;-)

import math

def factorial(i):
n = i + 1
return math.exp(-n)*(n**(n-0.5))*math.sqrt(2*math.pi)*(1. + 1./12/n +
1./288/n**2 - 139./51840/n**3)

Works for non integer factorials also...

See here for background

http://mathworld.wolfram.com/StirlingsSeries.html

Well, that's Sterling's formula. You do have to worry about
convergence/accuracy.

How about (for intergers - simple-minded version):

def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact

There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)

Then you could use,

arr=arange(i)+1
fact=arr.product() # or something like that

 

[mensanator]

Well, that's Sterling's formula. You do have to worry about
convergence/accuracy.

How about (for intergers - simple-minded version):

def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact

Simple minded indeed.

 

[marek.rocki]

Tim Golden napisa (a):

It's only a moment before the metaclass and
the Twisted solution come along.

I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes


class fact_0(object):
value = 1

class fact_meta(object):
def __new__(cls, name, bases, attrs):
n = attrs['n']
class_name = 'fact_%i' % n
try:
return globals()[class_name]
except KeyError:
new_class = type(class_name, bases, {})
new_class.value = n * fact(n - 1).value
new_class.__str__ = lambda self: str(self.value)
globals()[class_name] = new_class
return new_class

class fact(object):
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

print fact(5)
print fact(3)
print fact(1)

 

[mensanator]

Tim Golden napisa (a):

It's only a moment before the metaclass and
the Twisted solution come along.

I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes

class fact_0(object):
value = 1

class fact_meta(object):
def __new__(cls, name, bases, attrs):
n = attrs['n']
class_name = 'fact_%i' % n
try:
return globals()[class_name]
except KeyError:
new_class = type(class_name, bases, {})
new_class.value = n * fact(n - 1).value
new_class.__str__ = lambda self: str(self.value)
globals()[class_name] = new_class
return new_class

class fact(object):
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

print fact(5)
print fact(3)
print fact(1)

Dare I add fact(0)?

120
6
1
<__main__.fact_0 object at 0x011729F0>

Hmm..not sure what that means, but I bet I can't calculate
combinations.

What about fact(-1)?

120
6
1
<__main__.fact_0 object at 0x011729F0>

Traceback (most recent call last):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 31, in <module>
print fact(-1)
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, i

Wow! An infinite loop in the Traceback. Not quite the exception
I was looking for.

 

[Paul Rubin]

There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)

The "reduce" function which is being removed from python in 3.0.

import operator
def factorial(n):
return reduce(operator.mul, xrange(1,n+1))

 

[Paul Rubin]

I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes

It gets even weirder in Haskell.

http://www.willamette.edu/~fruehr/haskell/evolution.html

 

[Lou Pecora]

def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact

Simple minded indeed.
0.0
[/QUOTE]

Whoops, should have xrange(i)+1 there. Or, better, xrange(2,n+1). Save a
multiplication. Just trying to show the OP the scheme for iteration
here.

 

[Marco Mariani]

class fact_0(object):
value = 1 [...
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

You wrote lots of boilerplate to hide the fact you're cheating, didn't you?

The OP explicitly asked for an iterative procedure.

btw... writing a test unit to check the tested code is not calling
itself.. could be interesting

 

[Nicko]

The "reduce" function which is being removed from python in 3.0.

import operator
def factorial(n):
return reduce(operator.mul, xrange(1,n+1))

Since reduce is being removed, and Guido is known not to like its use
anyway, I propose the following code for Py2.5 and later:

import math
def fact(n):
return math.exp(sum((math.log(i) for i in range(1,n+1)))) if n

= 0 else None

If you don't like the rounding errors you could try:

def fact(n):
d = {"p":1L}
def f(i): d["p"] *= i
map(f, range(1,n+1))
return d["p"]

It is left as an exercise to the reader as to why this code will not
work on Py3K

Nicko

 

[Steven Bethard]

If you don't like the rounding errors you could try:

def fact(n):
d = {"p":1L}
def f(i): d["p"] *= i
map(f, range(1,n+1))
return d["p"]

It is left as an exercise to the reader as to why this code will not
work on Py3K

Serves you right for abusing map(). ;-)

STeVe

 

[Anurag]

What about this no map, reduce, mutiplication or even addition
Its truly interative and You will need to interate till infinity if
you want correct answer

def factorial(N):
"""
Increase I ...and go on increasing...
"""
import random

myNumer = range(N)
count = 0
I = 10000 #10**(N+1)
for i in range(I):
bucket = range(N)
number = []
for i in range(N):
k = bucket[ random.randrange(0,len(bucket))]
bucket.remove(k)
number.append(k)

if number == myNumer:
count+=1

return int(I*1.0/count+.5)

 

[Nick Craig-Wood]

What about this no map, reduce, mutiplication or even addition
Its truly interative and You will need to interate till infinity if
you want correct answer

def factorial(N):
"""
Increase I ...and go on increasing...
"""
import random

myNumer = range(N)
count = 0
I = 10000 #10**(N+1)
for i in range(I):
bucket = range(N)
number = []
for i in range(N):
k = bucket[ random.randrange(0,len(bucket))]
bucket.remove(k)
number.append(k)

if number == myNumer:
count+=1

return int(I*1.0/count+.5)

;-)

Note you can write your middle loop as

for i in range(I):
number = myNumer[:]
random.shuffle(number)
if number == myNumer:
count+=1

 

[Marco Mariani]

Note you can write your middle loop as

for i in range(I):
number = myNumer[:]
random.shuffle(number)
if number == myNumer:
count+=1

Nice. Try 'em all, then count 'em.

Another wtfery would be a SQLAlchemy solution, generating dynamic
queries, using only OUTER JOINs and COUNT(). Could be a way to justify
hardware upgrades.

 

[Boris Borcic]

I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

fact = lambda n : len(map([1].__imul__,range(1,n+1))[0])

hth

BB