function that counts...
in [Python]
|
From: Lie Ryan on 10 Jun 2010 10:34 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.
From: Bryan on 11 Jun 2010 16:19
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() |