function that counts...
in [Python]
|
From: Jean-Michel Pichavant on 25 May 2010 04:24 superpollo wrote: > Jean-Michel Pichavant ha scritto: >> Jerry Hill wrote: >>> On Wed, May 19, 2010 at 3:58 PM, superpollo <utente(a)esempio.net> 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""" >>> total = 0 >>> for testval in range(n): >>> sumofdigits = sum(int(char) for char in str(testval)) >>> if sumofdigits == m: >>> total += 1 >>> return total >>> >>> I added a docstring to the function, saying what it does, and what the >>> arguments are supposed to represent. I also moved the >>> convert-to-string-and-sum-the-digits logic into a single generator >>> expression that's passed to the builtin sum function. Oh, and I tried >>> to use slightly more expressive variable names. >>> >>> >> my favorite solutio nso far. >> >> @ OP >> >> What means prttn ? > > i already answered this downthreads... > >> something ... I don't find the word, something like un-intuitive. >> Sounds like homework. > > it is not. My apologies then, for both statements. 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. JM
From: superpollo on 25 May 2010 07:28 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 <utente(a)esempio.net> 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""" >>>> total = 0 >>>> for testval in range(n): >>>> sumofdigits = sum(int(char) for char in str(testval)) >>>> if sumofdigits == m: >>>> total += 1 >>>> return total >>>> >>>> I added a docstring to the function, saying what it does, and what the >>>> arguments are supposed to represent. I also moved the >>>> convert-to-string-and-sum-the-digits logic into a single generator >>>> expression that's passed to the builtin sum function. Oh, and I tried >>>> to use slightly more expressive variable names. >>>> >>>> >>> my favorite solutio nso far. >>> >>> @ OP >>> >>> What means prttn ? >> >> i already answered this downthreads... >> >>> something ... I don't find the word, something like un-intuitive. >>> Sounds like homework. >> >> it is not. > My apologies then, for both statements. > 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. > > JM ok, this is the mistery. it was inspired by a question on e.c.m.: http://groups.google.it/group/es.ciencia.matematicas/msg/f8f09672bd8a052a the first question is (somewhat) an instance of: http://en.wikipedia.org/wiki/Partition_(number_theory) bye
From: Bryan on 25 May 2010 19:40 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. -- --Bryan
From: Bryan on 25 May 2010 21:04 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 that sum to m. [1, 1, 2, 5] is a partition of 9. The problem at issue here is not that of counting partitions. My algorithm for our prttn separated out the 'ndsums' sub-problem: Count d-digit ints with digits summing to m. I found a generalization of that problem stated in the /CRC Handbook of Discrete and Combinatorial Mathematics/ (2000 edition, section 2.1) among "counting problems" as: Solutions to x_1 + ... x_n = k 0 <= x_i <= a_i for one or more i Alas, the handbook does not provide a formula or algorithm. It refers to the inclusion/exclusion principle, which I did not see how to turn into an efficient algorithm. My recursive memoizing method for ndsums() was initially a shot in the dark and I was surprised how well it worked. Thinking about it more, I can argue that it is polynomial-time based on the size of the memo- table and the work per entry. My prttn() calls ndsums() once for each digit, so the whole thing is polynomial in the number of digits. -- --Bryan
From: Bryan on 26 May 2010 04:03
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 |