Re: function that counts...

Discussion in 'Python' started by Jean-Michel Pichavant, May 24, 2010.

  1. 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 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 ? is it any Dutch word :D ? m & n are also very poors
    argument names.
    I will be difficult to name properly the function, as it is doing
    something ... I don't find the word, something like un-intuitive. Sounds
    like homework.

    def how_many_positive_integers_less_than_n_have_digits_that_sum_up_to_m(m, n)


    :eek:)

    JM

    PS : read http://tottinge.blogsome.com/meaningfulnames/

    <http://tottinge.blogsome.com/meaningfulnames/>
     
    Jean-Michel Pichavant, May 24, 2010
    #1
    1. Advertising

  2. 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):
    >>> """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
     
    Jean-Michel Pichavant, May 25, 2010
    #2
    1. Advertising

  3. Jean-Michel Pichavant

    Bryan Guest

    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
     
    Bryan, May 26, 2010
    #3
  4. Jean-Michel Pichavant

    Bryan Guest

    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
     
    Bryan, May 26, 2010
    #4
  5. Jean-Michel Pichavant

    Lie Ryan Guest

    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 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.


    superpollo posted this question in comp.programming
    (http://groups.google.com/group/comp...ead/thread/e3b10346db8ebd0a/579ca67f8b9b5a8c;
    http://groups.google.com/group/comp.programming/msg/f7323d6e6942e883;
    http://groups.google.com/group/comp...read/thread/e3b10346db8ebd0a/dc4cd1e2feb89500
    )

    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 next week, have been a little bit busy here)


    copying the code here for convenience:

    # memoization would be very useful here
    def fact(n):
    """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
    return n * fact(n - 1) if n != 0 else 1

    def C(n, r):
    """ regular Combination (nCr) """
    return fact(n) / (fact(n - r) * fact(r))

    def D(M, N):
    """ Distribution aka Partitioning """
    return C(M + N - 1, M)

    def partition10(M, i):
    """ Count how many integer < N sums to M where N = 10**int(i) """
    s = 0
    sign = 1
    for j in range(i + 1):
    s += sign * D(M, i) * C(i, j)

    # flip the sign for inclusion-exclusion
    sign *= -1

    # if M = 32, then 32, 22, 12, 2, -8
    M -= 10
    return s

    # still need to write:
    # def partitionN10(...): -- applies a "restriction"/"boundary" to
    # the most significant digit
    # then make it recurse.

    # assuming factorials calculation is constant time (hint: memoization)
    # the resulting code should work in O(n**2)
    # an improvement over the naive method which is O(10**n)
    # where n is the number of digits in N
    # DISCLAIMER: the big-O is a quick guess, not really calculated
     
    Lie Ryan, May 29, 2010
    #5
  6. Jean-Michel Pichavant

    Bryan Guest

    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 next week, have been a little bit busy here)
    >
    > copying the code here for convenience:
    >
    > # memoization would be very useful here
    > def fact(n):
    >     """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
    >     return n * fact(n - 1) if n != 0 else 1
    >
    > def C(n, r):
    >     """ regular Combination (nCr) """
    >     return fact(n) / (fact(n - r) * fact(r))
    >
    > def D(M, N):
    >     """ Distribution aka Partitioning """
    >     return C(M + N - 1, M)
    >
    > def partition10(M, i):
    >     """ Count how many integer < N sums to M where N = 10**int(i) """
    >     s = 0
    >     sign = 1
    >     for j in range(i + 1):
    >         s += sign * D(M, i) * C(i, j)
    >
    >         # flip the sign for inclusion-exclusion
    >         sign *= -1
    >
    >         # if M = 32, then 32, 22, 12, 2, -8
    >         M -= 10
    >     return s


    It doesn't seem to work. I get no answer at all, because it recursion-
    loops out when it calls fact() with a negative integer.

    --
    --Bryan
     
    Bryan, Jun 10, 2010
    #6
  7. Jean-Michel Pichavant

    Lie Ryan Guest

    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 won't be able to continue it
    >> until next week, have been a little bit busy here)
    >>
    >> copying the code here for convenience:
    >>
    >> # memoization would be very useful here
    >> def fact(n):
    >> """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
    >> return n * fact(n - 1) if n != 0 else 1
    >>
    >> def C(n, r):
    >> """ regular Combination (nCr) """
    >> return fact(n) / (fact(n - r) * fact(r))
    >>
    >> def D(M, N):
    >> """ Distribution aka Partitioning """
    >> return C(M + N - 1, M)
    >>
    >> def partition10(M, i):
    >> """ Count how many integer < N sums to M where N = 10**int(i) """
    >> s = 0
    >> sign = 1
    >> for j in range(i + 1):
    >> s += sign * D(M, i) * C(i, j)
    >>
    >> # flip the sign for inclusion-exclusion
    >> sign *= -1
    >>
    >> # if M = 32, then 32, 22, 12, 2, -8
    >> M -= 10
    >> return s

    >
    > It doesn't seem to work. I get no answer at all, because it recursion-
    > loops out when it calls fact() with a negative integer.


    Why of course you're right! 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

    when I reposted it here, I substituted that factorial to the recursive
    definition which fails when n is negative without much testing and that
    causes things to fails miserably. Sorry about that.
     
    Lie Ryan, Jun 10, 2010
    #7
  8. Jean-Michel Pichavant

    Bryan Guest

    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) gets the wrong answer when i is
    1 or 2. I think you don't want to let M go negative. With that tweak,
    it seems to work in general, and fact() never gets called with a
    negative number.

    What I really like about your partition10() is that it's adaptable to
    efficiently handle bases much larger than 10. Richard Thomas's
    algorithm is poly-time and efficient as long as the base is small.

    I'll take the liberty of tweaking your code to handle the 1 or 2 digit
    case, and write the more general form. I'll also memoize fact(), and
    add prttn() and a test.

    --
    --Bryan


    _ft = [1]
    def fact(n):
    assert n >= 0 and n % 1 == 0
    if len(_ft) <= n:
    for i in range(len(_ft), n + 1):
    _ft.append(i * _ft[-1])
    return _ft[n]

    def C(n, r):
    """ regular Combination (nCr) """
    return fact(n) // (fact(n - r) * fact(r))

    def D(M, N):
    """ Distribution aka Partitioning """
    assert M >= 0 and N > 0
    return C(M + N - 1, M)

    def partition(nballs, nbins, binmax):
    """Count ways to put identical balls into distinct bounded bins.
    """
    if nbins == 0:
    return int(nballs == 0)
    s = 0
    sign = 1
    for j in range(1 + min(nbins, nballs // binmax)):
    s += sign * D(nballs, nbins) * C(nbins, j)

    # flip the sign for inclusion-exclusion
    sign *= -1
    nballs -= binmax
    return s

    def prttn(m, n):
    assert m >= 0 and n > 0
    count = 0
    dls = [int(c) for c in reversed(str(n))]
    while dls:
    msd = dls.pop()
    count += sum(partition(m - d, len(dls), 10) for
    d in range(min(msd, m + 1)))
    m -= msd
    return count


    def test():
    upto = 123456
    counts = [0] * (len(str(upto)) * 9)
    for n in range(upto):
    digits = [int(c) for c in str(n)]
    counts[sum(digits)] += 1
    for m in range(9 * len(digits) + 2):
    count = prttn(m, n + 1)
    assert count == counts[m]
    if count == 0:
    break
    assert count == 0
    if n % 1000 == 0:
    print('Tested to:', n)

    test()
     
    Bryan, Jun 11, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. utab
    Replies:
    3
    Views:
    246
    Victor Bazarov
    Feb 17, 2006
  2. Jerry Hill

    Re: function that counts...

    Jerry Hill, May 19, 2010, in forum: Python
    Replies:
    2
    Views:
    283
    Steven D'Aprano
    May 19, 2010
  3. Steven D'Aprano

    Re: function that counts...

    Steven D'Aprano, May 19, 2010, in forum: Python
    Replies:
    5
    Views:
    336
    Albert van der Horst
    May 21, 2010
  4. Peter Pearson

    Re: function that counts...

    Peter Pearson, May 20, 2010, in forum: Python
    Replies:
    3
    Views:
    267
    Bryan
    May 26, 2010
  5. Raymond Hettinger

    Re: function that counts...

    Raymond Hettinger, May 24, 2010, in forum: Python
    Replies:
    2
    Views:
    320
    Bryan
    May 26, 2010
Loading...

Share This Page