Iteration for Factorials
Py-Fun
number using iteration and not recursion. Any simple ideas would be
appreciated.
Diez B. Roggisch
Show us your attempts, and we might suggest a fix. Because otherwise this
sounds suspiciously like homework.
Diez
Py-Fun
Here is my futile attempt. Be careful with this though, I just ran
something similar and it was never ending...
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")
itforfact(n)
Marco Mariani
As opposed to what, a complicated one?
Marco Mariani
> def itforfact(n):
> while n<100:
> print n
> n+1
> n = input("Please enter a number below 100")
You function should probably return something. After that, you can see
what happens with the result you get.
Duncan Booth
This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:
def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Py-Fun
Marco, Thanks for the tip. This now works:
def itforfact(n):
while n<100:
print n
n = n+1
n = input("Please enter a number below 100")
itforfact(n)
Is it a "factorial" though?
cokof...@gmail.com
lambda n: n<=0 or reduce(lambda a,b: long(a)*long(b),xrange(1,n+1))
Amit Khemka
Let me give you a pseudo code (which though can be found in most of
the textbooks and some 'simple' googling). Try to understand the code
and then write an equivalent python function.
function iFactorial(n: integer): integer;
var i, temp: integer;
begin
temp = 1;
for i = 1 to n do
temp = temp * i
end
return temp
About your code.
1. why doesn't it surprise you if the code that you posted goes in
infinite loop ?!
2. why do you use condition: n < 100
3. How do you think that your function will calculate the factorial ?
4. Instead of "input" use "raw_input", and then "cast" the input as integer .
Cheers,
amit.
--
--
Amit Khemka
vimal
i am just suggesting u an idea
but i dont know it satisfies ur needs
x=10
def cal_range(10)
for i in range(10):
print 2**i
Ant
> 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.
The following simple adder functions should give you an idea of how
recursion can be recast as iteration:
def acc(i):
'''i should be a positive integer'''
if i > 0:
return i + acc(i - 1)
return 0
print "acc", acc(9)
def itt(i):
'''i should be a positive integer'''
out = 0
while i > 0:
out += i
i = i - 1
return out
print "itt", itt(9)
> ...
> Is it a "factorial" though?
Er, no. And neither is mine. You may want to google for the definition
of factorial! Here's a hint:
reduce(operator.mul, range(1, i + 1))
--
Anthony Roy
Marco Mariani
It satisfies the requirements nicely ;)
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
def tail_recursion(g):
'''
Version of tail_recursion decorator using no stack-frame
inspection.
'''
loc_vars ={"in_loop":False,"cnt":0}
def result(*args, **kwd):
loc_vars["cnt"]+=1
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except (TypeError, ValueError):
loc_vars["in_loop"] = False
return tc
else:
if loc_vars["cnt"]%2==0:
return ('continue',args, kwd)
else:
return g(*args,**kwd)
return result
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res
Marco Mariani
>> From the cookbook, this time.
>> It satisfies the requirements nicely ;)
>>
>> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
>
> [... snip the ultimate general-purpose answer to the OP's question ...
>
> I really hope that's a wink up there, Marco.
The wink is in the second line of my post... more for the "do the least
amount of work to meet the requirements" people that for the OP
> The poor guy was just trying to get his homework done!
I don't see how my answer is in any way worse than those based on
lambda. Maybe I'm just envious because when I was his age I couldn't
google for answers. He should at least be able to do that, shouldn't he?
But wait. That would mean understanding what a factorial is. That would
require a second search, or a textbook, or an understanding of
arithmetics before programming with or without recursion. Should we
blame the teachers?
Peter Goodman
def fac_btt(num):
total = 1
if num > 1:
for i in range(1, num+1):
total *= i
return total
Paul McGuire
Maybe a little math refresher would be good for those trying to post
suggestions.
"Factorial of N" means "the product of 1 x 2 x 3 x ... x N", and is
shown symbolically as "N!".
(Factorial is only defined for nonnegative numbers, and for reasons
that go beyond this little note, just know that 0! = 1.)
In Python, a fully expanded factorial for values >= 1 would be:
2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5
8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
Here is an example routine showing iteration, that prints these
expressions:
def print_factorial(n):
print str(n)+"! =",
print "1",
t = 2
while t <= n:
print "*",t,
t += 1
print
Perhaps this example will give you some ideas on how to approach your
problem.
-- Paul
Tim Golden
> Tim Golden wrote:
>
>>> From the cookbook, this time.
>>> It satisfies the requirements nicely ;)
>>>
>>> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
>> [... snip the ultimate general-purpose answer to the OP's question ...
>>
>> I really hope that's a wink up there, Marco.
>
> The wink is in the second line of my post...
I did see it :)
>> The poor guy was just trying to get his homework done!
>
> I don't see how my answer is in any way worse than those based on
> lambda.
Nor do I. I was just joking with a colleague that the guy
just wanted a bit of help (which he did get, in fact from
several sources) and then out came the lambda and the
decorator. It's only a moment before the metaclass and
the Twisted solution come along. :)
(It's like watching a convention of lisp programmers --
ducks, runs for cover)
TJG
mensa...@aol.com
Not simple enough for my taste:
>>> import gmpy
>>> gmpy.fac(10)
mpz(3628800)
Michael J. Fromberger
Py-Fun <lorna...@gmail.com> wrote:
Well, first think about the recursive implementation:
def fact(n):
if n > 0:
return n * fact(n - 1)
else:
return 1
To turn this into an iterative computation, you must first get rid of
the deferred operations -- in this case, the multiplication step after
the recursive call to fact(n - 1).
Since multiplication commutes, we can re-write this recursion to keep an
accumulating parameter instead of deferring the operation:
def fact2(n, acc = 1):
if n > 0:
return fact2(n - 1, acc * n)
else:
return acc
This is a little bit better, because now the recursive call is in tail
position, and so in principle no state needs to be saved across
recursive calls: Once the inner call to fact2 is complete, its value is
simply returned. But we're not done yet, because Python _does_ save
state across recursive calls, even in this construction.
By a gentle twist of perspective, the inner call to "fact2(n - 1, acc *
n)" is really just a kind of "jump" back to the beginning of the
function. In another (hypothetical) language, you might write it like
this:
# Not legal Python code.
def fact3(n, acc = 1):
TOP:
if n > 0
n = n - 1
acc = acc * n
goto TOP
else:
return acc
Naturally, of course, Python does not provide a "goto" statement. But
it does have one that's similar:
while TEST: BODY
is equivalent in meaning to the pseudo-code:
X: if TEST:
BODY
goto X
Can you now see how you would re-write "fact3" into legal Python code,
using this equivalence? Once you have done so, you will also be able to
get rid of the extra accumulating parameter, and then you will have what
you wanted.
I hope this helps.
Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
Paul Rudin
I haven't followed all this thread, but has anyone yet done:
import operator
def fact(x):
return reduce(operator.mul, xrange(1,x))
Steven Bethard
> # Not legal Python code.
> def fact3(n, acc = 1):
> TOP:
> if n > 0
> n = n - 1
> acc = acc * n
> goto TOP
> else:
> return acc
Yes, to write this in legal Python code, you have to write::
from goto import goto, label # http://entrian.com/goto/
def fact3(n, acc = 1):
label .TOP
if n > 0
n = n - 1
acc = acc * n
goto .TOP
else:
return acc
;-)
STeVe
mensa...@aol.com
I hope not.
>>> import operator
>>> def fact(x):
return reduce(operator.mul,xrange(1,x))
>>> fact(3)
2
>>> fact(2)
1
>>> fact(1)
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
fact(1)
File "<pyshell#7>", line 2, in fact
return reduce(operator.mul,xrange(1,x))
TypeError: reduce() of empty sequence with no initial value
>>> fact(0)
Traceback (most recent call last):
File "<pyshell#11>", line 1, in <module>
fact(0)
File "<pyshell#7>", line 2, in fact
return reduce(operator.mul,xrange(1,x))
TypeError: reduce() of empty sequence with no initial value
I think you need to make it a bit more complicated.
tok...@gmail.com
> import operator
> def fact(x):
> return reduce(operator.mul, xrange(1,x))
Maybe:
import operator
def fact(x):
return reduce(operator.mul, xrange(2, x+1), 1)
fact(0)
1
fact(4)
24
Tim Chase
> if x == 0 or x == 1:
> return 1
> else:
> return reduce(operator.mul, xrange(1,x+1))
If obscurity is the name of the game,
>>> from operator import mul
>>> fact = lambda i: i > 1 and reduce(mul, xrange(1,i+1)) or i
>= 0 and 1 or None
>>> for i in xrange(-2,10): print '%i! = %s' % (i, fact(i))
My eyes hurt after reading that...as the order of operations is
left to Python to discern (a few judiciously placed parens might
improve things...though that may be like polishing coprolite)
I haven't yet seen an implementation in C (using the python/C
interface) or anybody handing off a python AST/opcode-list to an
appropriate function :)
-tkc
Paul Rudin
mensa...@aol.com
Nope, still doesn't work:
>>> def fact(x):
return reduce(operator.mul,xrange(1,x+1),1)
>>> fact(3)
6
>>> fact(2)
2
>>> fact(1)
1
>>> fact(0)
1
>>> fact(-1)
1
>>> fact(-2)
1
>>> fact(-3)
1
fact() should raise an exception if x is negative.
My variant of your original (same as Tim Chase's except the
test for x==1 is not necessary):
>>> def fact(x):
if x==0:
return 1
else:
return reduce(operator.mul,xrange(1,x+1))
>>> fact(3)
6
>>> fact(2)
2
>>> fact(1)
1
>>> fact(0)
1
>>> fact(-1)
Traceback (most recent call last):
File "<pyshell#40>", line 1, in <module>
fact(-1)
File "<pyshell#35>", line 5, in fact
return reduce(operator.mul,xrange(1,x+1))
mensa...@aol.com
> > def fact(x):
> > if x == 0 or x == 1:
> > return 1
> > else:
> > return reduce(operator.mul, xrange(1,x+1))
>
> If obscurity is the name of the game,
>
> >>> from operator import mul
> >>> fact = lambda i: i > 1 and reduce(mul, xrange(1,i+1)) or i
> >= 0 and 1 or None
> >>> for i in xrange(-2,10): print '%i! = %s' % (i, fact(i))
>
> My eyes hurt after reading that...as the order of operations is
> left to Python to discern (a few judiciously placed parens might
> improve things...though that may be like polishing coprolite)
Indeed. Particularly since it doesn't work:
-2! = -2
-1! = -1
0! = 0
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
0! is defined to be 1. You'll have a hard time calculating
combinations if 0! returns 0. Also, fact() should raise an
exception when x is negative.
It not only has to work correctly, it has to fail correctly also.
mensa...@aol.com
> On Oct 22, 3:38 pm, Paul Rudin <paul.nos...@rudin.co.uk> wrote:
>
>
>
>
>
> > tokl...@gmail.com writes:
> > > On 22 oct, 20:35, Paul Rudin <paul.nos...@rudin.co.uk> wrote:
>
> > >> import operator
> > >> def fact(x):
> > >> return reduce(operator.mul, xrange(1,x))
>
> > > Maybe:
>
> > > import operator
> > > def fact(x):
> > > return reduce(operator.mul, xrange(2, x+1), 1)
>
> > Or just:
>
> > reduce(operator.mul, xrange(1, x), 1)
>
> Nope, still doesn't work:
>
> >>> def fact(x):
>
> return reduce(operator.mul,xrange(1,x+1),1)
Excuse me, I mistyped your proposed solution. You had
xrange(1,x) not xrange(1,x+1). The former only returns
correct factorials for x==0 and x==1.
Sorry for the confusion.
> TypeError: reduce() of empty sequence with no initial value- Hide quoted text -
>
> - Show quoted text -
Tim Chase
>>
>> >>> from operator import mul
>> >>> fact = lambda i: i > 1 and reduce(mul, xrange(1,i+1)) or i
>> >= 0 and 1 or None
>> >>> for i in xrange(-2,10): print '%i! = %s' % (i, fact(i))
>>
>> My eyes hurt after reading that...as the order of operations is
>> left to Python to discern (a few judiciously placed parens might
>> improve things...though that may be like polishing coprolite)
>
> Indeed. Particularly since it doesn't work:
Huh? Works on the Python (2.4) I have, both the Win32 python at
work and Linux Python at home:
>>> from operator import mul
>>> fact = lambda i: i > 1 and reduce(mul, xrange(1, i+1)) or i
>= 0 and 1 or None
>>> for i in xrange(-2,10): print '%i! = %s' % (i, fact(i))
...
-2! = None
-1! = None
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
It could even be more obscure by making it
>>> fact = lambda i: i > 1 and reduce(mul, xrange(1, i+1)) or not
i and 1 or None
Stunts like this would get a person fired around here if they
were found in production code :)
-tkc
mensa...@aol.com
> >> If obscurity is the name of the game,
>
> >> >>> from operator import mul
> >> >>> fact = lambda i: i > 1 and reduce(mul, xrange(1,i+1)) or i
> >> >= 0 and 1 or None
> >> >>> for i in xrange(-2,10): print '%i! = %s' % (i, fact(i))
>
> >> My eyes hurt after reading that...as the order of operations is
> >> left to Python to discern (a few judiciously placed parens might
> >> improve things...though that may be like polishing coprolite)
>
> > Indeed. Particularly since it doesn't work:
>
> Huh? Works on the Python (2.4) I have, both the Win32 python at
> work and Linux Python at home:
Sorry about that, Google line wrapped the fact definition
and it worked anyway in Idle (but not as written).
Still, why do you want None instead of raisng an exception
(as is the case in other factorial implementations)?
Tim Chase
> (as is the case in other factorial implementations)?
A null value is as good/bad as raising an exception in my book.
Since you can't do math on a None object, any attempt to do so
will raise an exception:
>>> 42 + fact(-1)
I generally prefer my functions to return semi-sensible results
(in this case, None makes sense to me, as there isn't really a
definition of "negative-one factorial"). It also fits in my head
alongside my SQL where NULL values/expressions can be returned
and evaluated without the whole query falling over.
I suppose if you really wanted to throw an exception using this
lambda craziness, you could wrap the whole result in "0 +
([body])" which, if the body returned Null, would push up
exception daisies (with slightly misleading exception information).
-tkc
Hendrik van Rooyen
> I don't see how my answer is in any way worse than those based on
> lambda. Maybe I'm just envious because when I was his age I couldn't
> google for answers. He should at least be able to do that, shouldn't he?
> But wait. That would mean understanding what a factorial is. That would
> require a second search, or a textbook, or an understanding of
> arithmetics before programming with or without recursion. Should we
> blame the teachers?
Yes. And burn their cars to get their attention!
Asking someone to write a factorial algorithm before he knows WTF a
factorial "is", is either insane, or the ultimate demonstration of deliberate
lack of cooperation and coordination between departments.
I feel kind of strongly about this ever since, as a student, the physics people
expected me to use mathematics that I had not been taught yet...
;-)
I shall try to refrain from commenting on the concept of introducing
recursion into a first course in CS - I am too much tainted by my ability
to mentally "see" the stack growth in a small processor to be qualified
to comment.
- Hendrik
cokof...@gmail.com
Completely agree with this point of view. After being on the receiving
end of such problems when first introduced to Haskell and told to look
at a database written in it and work my way through it (without having
started the course on databases, locks, or any of that jargon) you
find yourself almost helpless at times.
Hard to google for something you don't know about.
Recursive calling is a fun, and yet painful, thing...
Marco Mariani
>>>> fact = lambda i: i > 1 and reduce(mul, xrange(1, i+1)) or not
> i and 1 or None
>
> Stunts like this would get a person fired around here if they
> were found in production code :)
eheh, indeed.
def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1
tok...@gmail.com
> Nope, still doesn't work:
>
> def fact(x):
> return reduce(operator.mul,xrange(1,x+1),1)
>
> fact() should raise an exception if x is negative.
So, where is the problem? if not allowing negative numbers is so
important for you, add a if statement and raise a ValueError exception.
cokof...@gmail.com
indeed, especially considering that fact(x) is essentially just a
lambda statement as Marco Mariani said.
Roberto Bonvallet
> Er, no. And neither is mine. You may want to google for the definition
> of factorial!
Don't google for the definition... google for the answer!
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%%21"
% x):
m = r.search(line)
if m:
return int(m.group(1))
--
Roberto Bonvallet
Hendrik van Rooyen
> >
> Heh... the one saving grace of taking a CS major in a period where
> the primary languages taught were FORTRAN (IV), COBOL (74), and
> something close to K&K BASIC. Heck, even the assembler class followed
> the FORTRAN parameter handling scheme (argument addresses copied to
> static locals and used via one level of indirection) -- It would take me
> some time, today, to figure out how to even create a "stack" (even the
> return address was passed via a reserved register and saved locally):
>
> call,2 sub-address
> data arg1-address
> data arg2-address
> do-something
> .
> .
> .
> sub-address: store,2 my-return
> load,9 *my-return,1 ;indexed access
> store,9 param1
> load,9 *my-return,2
> store,9 param2
> do-stuff
> load,2 my-return
> addimmediate,2 2 ;number of args to
> adjust return
> return,2
>
> (format:
> label command,register argument
> *argument ;indirection
> argument,x ;indexed )
> --
Yuk. Reminds me of one of the Hitachi processors that
has a single depth hardware "link register" that tells a
subroutine where it was called from.
I was thinking of a stack that grows when you call or push,
and shrinks when you return or pop.
When there are only 128 or so bytes, and an address is two bytes,
recursive calling soon runs into trouble. Especially so if you also
use the stack to pass params...
- Hendrik
Jon Ribbens
> Yuk. Reminds me of one of the Hitachi processors that
> has a single depth hardware "link register" that tells a
> subroutine where it was called from.
That's how ARM processors work, and they're everywhere these days.
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%%21" % 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
mensa...@aol.com
> On 22 oct, 23:39, "mensana...@aol.com" <mensana...@aol.com> wrote:
>
> > Nope, still doesn't work:
>
> > def fact(x):
> > return reduce(operator.mul,xrange(1,x+1),1)
>
> > fact() should raise an exception if x is negative.
>
> 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?
mensa...@aol.com
Needs work.
IDLE 1.2
>>> def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1
>>> fact(3)
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
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
--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick
Lou Pecora
Nick Craig-Wood <ni...@craig-wood.com> wrote:
> Py-Fun <lorna...@gmail.com> wrote:
> > 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
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
--
-- Lou Pecora
mensa...@aol.com
> In article <slrnfhvalj.67s.n...@irishsea.home.craig-wood.com>,
> Nick Craig-Wood <n...@craig-wood.com> wrote:
>
>
>
>
>
> > Py-Fun <lorna.bu...@gmail.com> wrote:
> > > 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
>
> 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.
>>> factorial(3)
0.0
>
> 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
>
> --
> -- Lou Pecora- Hide quoted text -
marek...@wp.pl
> 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)
mensa...@aol.com
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
> > 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 :-)
It gets even weirder in Haskell.
Lou Pecora
"mensa...@aol.com" <mensa...@aol.com> wrote:
> > def factorial(i):
> > fact=1.0
> > for n in xrange(i):
> > fact=n*fact
> > return fact
>
> Simple minded indeed.
>
> >>> factorial(3)
> 0.0
>
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.
--
-- Lou Pecora
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
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
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
;-)
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
auz...@gmail.com
>
> - Show quoted text -
good :) i thinkif go on improving this we will have worlds' best
useless factorial function.
actually number = myNumer[:] can be moved out of the loop.
J. Clifford Dyer
Nice one. I was trying to grok it, and started out by breaking it down:
>>> [1].__imul__(2)
[1, 1]
>>> map([1].__imul__,range(1,3))
[[1, 1], [1, 1]]
So far so good, but I tried to break it down a little more:
>>> [1].__imul__(1), [1].__imul__(2), [1].__imul__(3)
([1], [1, 1], [1, 1, 1])
Hmm. Wasn't what I was expecting.
Then it hit me:
>>> L = [1]
>>> L.__imul__(1), L.__imul__(2), L.__imul__(3)
([1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1])
Pretty sneaky, sis.
Cheers,
Cliff
P.S. Regards to those who lack a grounding in American pop-culture, or who are to young to remember the origins of "Pretty sneaky, sis."
J. Clifford Dyer
>
OK. Now I've been sucked in. How about this:
def fact(x):
def f(x):
if int(x) != x:
raise ValueError
elif x > 1:
return f(x-1) ** x
elif x == 1:
return 10
else:
raise ValueError
return len(str(f(x))) -1
The great part about this recursive solution is that you don't have to worry about the stack limit because performance degrades so quickly on the conversion to string! fact(8) takes a little less than a second, fact(9) takes about a minute, and fact(10) takes more time than I had patience to wait for!
Cheers,
Cliff
mensa...@aol.com
And the not-so-great part is that it raises an exception
on fact(0) which makes it utterly useless for calculating
combinations of m things taken n at a time: m!/n!*(m-n)!
Why is it that no one seems able to get this right?
>
> Cheers,
> Cliff
J. Clifford Dyer
I can't speak for everyone, but my excuses are as follows:
* I haven't studied math or done math-heavy work in 8 years.
* I'm not at my home computer, and most of the thread (wherein, I now recall, that particular rule was specified) is downloaded to my home computer, so I was working from my feeble memory.
* I didn't care enough to google for it.
That said, s/elif x == 1:/elif x in (0,1):/ should solve the problem
mensa...@aol.com
Fair enough. I primarily do math-heavy work, and am familiar
with such matters. But that's just me.
> * I'm not at my home computer, and most of the thread (wherein,
> I now recall, that particular rule was specified) is downloaded
> to my home computer, so I was working from my feeble memory.
Well, I've only had to point it out a dozen times already in
this thread. Nice to see that all that effort has been for nought.
> * I didn't care enough to google for it.
Quoting from Monty Python:
"It's just as easy to get these things right, you know."
>
> That said, s/elif x == 1:/elif x in (0,1):/ should solve the problem
Sure, it's always easily solvable. I just hope someone learns the
lesson on how to test properly, to make sure things work the way
they should and to fail the way they should so that one can actually
trust the algorithms they write.
Gabriel Genellina
<mensa...@aol.com> escribió:
Uhmmm... don't be so serious, most of those recipes are a joke :)
Who cares about fact(0) when fact(10) can't be computed...? At least,
that's how I see it, Nimo dixit.
--
Gabriel Genellina