function that counts...
in [Python]
|
From: Bryan on 26 May 2010 04:30 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
From: Albert van der Horst on 26 May 2010 10:32 In article <4bf442cd$0$31377$4fafbaef(a)reader1.news.tin.it>, superpollo <utente(a)esempio.net> 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]) > if sum == m: > tot += 1 > return tot > .....: > >In [207]: prttn(25, 10000) >Out[207]: 348 > >any suggestion for pythonizin' it? I don't like the excursion to string and back. def x(i) : return x(i/10)+i%10 if i else 0 or if you can't stand recursion: def x(i): s= 0 while i: s += i%10 i /= 10 return s (All untested but you get the idea.) > >bye -- -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert(a)spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
From: Lie Ryan on 28 May 2010 20:23 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.programming/browse_thread/thread/e3b10346db8ebd0a/579ca67f8b9b5a8c; http://groups.google.com/group/comp.programming/msg/f7323d6e6942e883; http://groups.google.com/group/comp.programming/browse_thread/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
From: Albert van der Horst on 9 Jun 2010 05:57 In article <l3172q.b4n(a)spenarnc.xs4all.nl>, Albert van der Horst <albert(a)spenarnc.xs4all.nl> wrote: >In article <4bf442cd$0$31377$4fafbaef(a)reader1.news.tin.it>, >superpollo <utente(a)esempio.net> 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]) >> if sum == m: >> tot += 1 >> return tot >> .....: >> >>In [207]: prttn(25, 10000) >>Out[207]: 348 >> >>any suggestion for pythonizin' it? > >I don't like the excursion to string and back. > >def x(i) : return x(i/10)+i%10 if i else 0 Can't be made to work easily. > >or if you can't stand recursion: > >def x(i): > s= 0 > while i: > s += i%10 > i /= 10 > return s The above doesn't work. This one has been tested: " def x(i): s= 0 while i: s *= 10 s += i%10 i /= 10 return s " (With as loop-invariant the concatenation of i and reversed-s and as loop-variant i) Groetjes Albert -- -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert(a)spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
From: Bryan on 9 Jun 2010 19:03
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 |