Lie Ryan wrote:
> In my original post in comp.programming, I
> used this definition of factorial:
>
> def fact(n):
> """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
> p = 1
> for i in range(1,n+1):
> p *= i
> return p
Ah, much better, but partition10(M, i) ge
On 06/10/10 09:03, Bryan wrote:
> Lie Ryan wrote:
>> I went through the mathematical foundation of using
>> partition/distribution and inclusion-exclusion, and have written some
>> code that solves a subset of the problem, feel free if you or superpollo
>> are interested in continuing my answer (I
Lie Ryan wrote:
> I went through the mathematical foundation of using
> partition/distribution and inclusion-exclusion, and have written some
> code that solves a subset of the problem, feel free if you or superpollo
> are interested in continuing my answer (I won't be able to continue it
> until n
In article ,
Albert van der Horst wrote:
>In article <4bf442cd$0$31377$4fafb...@reader1.news.tin.it>,
>superpollo wrote:
>>... how many positive integers less than n have digits that sum up to m:
>>
>>In [197]: def prttn(m, n):
>> tot = 0
>> for i in range(n):
>> s = str(i)
>>
On 05/26/10 11:04, Bryan wrote:
> Jean-Michel Pichavant wrote:
>> I still don't see "how many positive integers less than n have digits
>> that sum up to m" makes it a "partition" though if that what prttn
>> means. Surely because I miss the context.
>
> A partition of a positive integer m is an u
In article <4bf442cd$0$31377$4fafb...@reader1.news.tin.it>,
superpollo wrote:
>... how many positive integers less than n have digits that sum up to m:
>
>In [197]: def prttn(m, n):
> tot = 0
> for i in range(n):
> s = str(i)
> sum = 0
> for j in range(len(s)):
>
I wrote:
> > I came up with a recursive memo-izing algorithm that
> > handles 100-digit n's.
Oops. I missed Richard Thomas's post. He posted the same algorithm a
couple days before.
--
--Bryan
--
http://mail.python.org/mailman/listinfo/python-list
I wrote:
> My prttn() calls ndsums() once for each
> digit, so the whole thing is polynomial in the number of digits.
Correction: my prttn() function calls ndsums() at most 9 times per
digit of n. That still provides run time polynomial in the length of
the input.
--
--Bryan
--
http://mail.pyth
Jean-Michel Pichavant wrote:
> I still don't see "how many positive integers less than n have digits
> that sum up to m" makes it a "partition" though if that what prttn
> means. Surely because I miss the context.
A partition of a positive integer m is an unordered collection of
positive integers
Raymond Hettinger wrote:
> If speed is important, the global lookups can be localized:
>
> def prttn(m, n, map=itertools.imap, int=int, str=str, range=range):
> return sum(m == sum(map(int, str(x))) for x in range(n))
That's just silly. "If speed is important," we abandon the naive
algorithm.
Jean-Michel Pichavant ha scritto:
superpollo wrote:
Jean-Michel Pichavant ha scritto:
Jerry Hill wrote:
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
... how many positive integers less than n have digits that sum up
to m:
...
any suggestion for pythonizin' it?
This is
superpollo wrote:
Jean-Michel Pichavant ha scritto:
Jerry Hill wrote:
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
... how many positive integers less than n have digits that sum up
to m:
...
any suggestion for pythonizin' it?
This is how I would do it:
def prttn(m, n
Jean-Michel Pichavant ha scritto:
Jerry Hill wrote:
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
...
any suggestion for pythonizin' it?
This is how I would do it:
def prttn(m, n):
"""How many
What about avoiding the string conversion and use mod/div operations
in order to create a list of digits for a number?
Now that you have the sequences it's easy to count which sums up to m.
On Mon, May 24, 2010 at 4:14 PM, Raymond Hettinger wrote:
> On May 19, 12:58 pm, superpollo wrote:
>> ...
Jerry Hill wrote:
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
...
any suggestion for pythonizin' it?
This is how I would do it:
def prttn(m, n):
"""How many positive integers less than n hav
On May 19, 12:58 pm, superpollo wrote:
> ... how many positive integers less than n have digits that sum up to m:
>
> In [197]: def prttn(m, n):
> tot = 0
> for i in range(n):
> s = str(i)
> sum = 0
> for j in range(len(s)):
> sum += int(s[j])
>
I wrote:
> I came up with a recursive memo-izing algorithm that
> handles 100-digit n's.
[...]
I made a couple improvements. Code below.
-Bryan
#-
_nds = {}
def ndsums(m, d):
""" Count d-digit ints with digits suming to m.
"""
assert m >= 0 and d >= 0
m = min
Peter Pearson wrote:
> If it's important for the function to execute quickly for large n,
> you might get a useful speedup by testing only every ninth integer,
Our standards for "quickly" and "large" seem kind of thin.
> I suspect that further applications of number theory would
> provide additio
In article ,
Grant Edwards wrote:
>
>Lest my allusions to Fortran IV be lost upon the less grizzled, only
>the first 6 characters were significant in Fortran IV identifiers, and
>removing all of the vowels from a longer word was an idiomatic way to
>create an identifier with a length <= 6.
>
>IIR
On Thu, 20 May 2010 19:53:42 + (UTC)
Grant Edwards wrote:
> Since Python is interactive, and you don't get charged for each time
> you run your deck through the reader, that's easy enough to check:
Whoa! For a moment there I thought it was 1969. :-)
--
D'Arcy J.M. Cain | Democra
On 2010-05-20, superpollo wrote:
> Grant Edwards ha scritto:
>> On 2010-05-20, superpollo wrote:
>>> Steven D'Aprano ha scritto:
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
> ... how many positive integers less than n have digits that sum up to m:
Does the name "
Grant Edwards ha scritto:
On 2010-05-20, superpollo wrote:
Steven D'Aprano ha scritto:
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
In [197]: def prttn(m, n):
Does the name "prttn" mean anything? I'm afraid I
On 2010-05-20, superpollo wrote:
> Steven D'Aprano ha scritto:
>> On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
>>
>>> ... how many positive integers less than n have digits that sum up to m:
>>>
>>> In [197]: def prttn(m, n):
>>
>> Does the name "prttn" mean anything? I'm afraid I keep
Peter Pearson ha scritto:
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
If it's important for the function to execute quickly for large n,
you might get a useful speedup by testing only every ninth integer,
since
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
> ... how many positive integers less than n have digits that sum up to m:
If it's important for the function to execute quickly for large n,
you might get a useful speedup by testing only every ninth integer,
since any two integers whose digi
Richard Thomas ha scritto:
For this kind of problem you should avoid all that stringification. I
find it best to deal with sequences of digits of a fixed length and go
from there. For example:
def count1(m, n, cache={}):
"""Number of digit sequences of length `n` summing to `m`."""
if n
Steven D'Aprano ha scritto:
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
In [197]: def prttn(m, n):
Does the name "prttn" mean anything? I'm afraid I keep reading it as a
mispelling of "print n".
pArtItIOn
Steven D'Aprano ha scritto:
On Wed, 19 May 2010 22:58:22 +0200, superpollo wrote:
In [266]: del(sum)
del is a statement, not a function, so the brackets are pointless. This
is like writing:
x = (1)
instead of
x = 1
`del sum` is all you need.
sorry about that, thanks a lot!
bye
--
ht
On 5/19/2010 5:51 PM, Steven D'Aprano wrote:
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
Rather than iterating over an index j = 0, 1, 2, ... and then fetching
the jth character of the string, you can iterate over the characters
directly. So the inner loop is better written:
for c in
For this kind of problem you should avoid all that stringification. I
find it best to deal with sequences of digits of a fixed length and go
from there. For example:
def count1(m, n, cache={}):
"""Number of digit sequences of length `n` summing to `m`."""
if n < 0 or m < 0:
return
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
> ... how many positive integers less than n have digits that sum up to m:
>
> In [197]: def prttn(m, n):
Does the name "prttn" mean anything? I'm afraid I keep reading it as a
mispelling of "print n".
[...]
> s = str(i)
>
On Wed, 19 May 2010 22:58:22 +0200, superpollo wrote:
> In [266]: del(sum)
del is a statement, not a function, so the brackets are pointless. This
is like writing:
x = (1)
instead of
x = 1
`del sum` is all you need.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
Am 19.05.2010 22:58, schrieb superpollo:
>
> In [277]: prttn(25, 1)
> Out[277]: 348
>
> In [278]: prttn2(25, 1)
> Out[278]: 348
>
> In [279]: prttn3(25, 1)
> Out[279]: 348
>
> ok, bye!
Just because I was curios:
nec...@zakarumiy ~ % python -m timeit "import test; test.prttn(25,100
Mark Dickinson ha scritto:
On May 19, 9:30 pm, superpollo wrote:
René 'Necoro' Neumann ha scritto:
An idea would be:
def prttn(m, n):
...return sum(1 for x in range(n) if sum(map(int, str(x))) == m)
TypeError: 'int' object is not callable
on 2.5.4
The TypeError is almost certainl
Jerry Hill ha scritto:
On Wed, May 19, 2010 at 4:25 PM, superpollo wrote:
Jerry Hill ha scritto:
sumofdigits = sum(int(char) for char in str(testval))
this line gives me this:
TypeError: 'int' object is not callable
is it some new feature in >2.5 ?
No, sum() has been a builtin sinc
On May 19, 9:30 pm, superpollo wrote:
> René 'Necoro' Neumann ha scritto:
> > An idea would be:
>
> def prttn(m, n):
> > ... return sum(1 for x in range(n) if sum(map(int, str(x))) == m)
>
> TypeError: 'int' object is not callable
>
> on 2.5.4
The TypeError is almost certainly because
On Wed, May 19, 2010 at 4:25 PM, superpollo wrote:
> Jerry Hill ha scritto:
>> sumofdigits = sum(int(char) for char in str(testval))
>
> this line gives me this:
>
> TypeError: 'int' object is not callable
>
> is it some new feature in >2.5 ?
No, sum() has been a builtin since Python 2.3.
René 'Necoro' Neumann ha scritto:
Am 19.05.2010 21:58, schrieb superpollo:
... how many positive integers less than n have digits that sum up to m:
In [197]: def prttn(m, n):
tot = 0
for i in range(n):
s = str(i)
sum = 0
for j in range(len(s)):
sum +=
Jerry Hill ha scritto:
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
... how many positive integers less than n have digits that sum up to m:
...
any suggestion for pythonizin' it?
This is how I would do it:
def prttn(m, n):
"""How many positive integers less than n have digits th
Am 19.05.2010 21:58, schrieb superpollo:
> ... how many positive integers less than n have digits that sum up to m:
>
> In [197]: def prttn(m, n):
> tot = 0
> for i in range(n):
> s = str(i)
> sum = 0
> for j in range(len(s)):
> sum += int(s[j])
>
On Wed, May 19, 2010 at 3:58 PM, superpollo wrote:
> ... how many positive integers less than n have digits that sum up to m:
...
> any suggestion for pythonizin' it?
This is how I would do it:
def prttn(m, n):
"""How many positive integers less than n have digits that sum up to m"""
tot
... how many positive integers less than n have digits that sum up to m:
In [197]: def prttn(m, n):
tot = 0
for i in range(n):
s = str(i)
sum = 0
for j in range(len(s)):
sum += int(s[j])
if sum == m:
tot += 1
return tot
.:
42 matches
Mail list logo
