Removing Recursion

[Ignacio Vazquez-Abrams]

On Mon, 24 Sep 2001, Duncan Smith wrote:

> Thanks, but I'm still struggling.  Your code might help me speed up a
> related function, but I don't think it achieves the same as my original code
> (unless I've hacked it to bits:-)).  eg. the following.
>
> >>> import problem
> >>> z = MyClass(3,8)
> >>> z.bins()
> [1, 1, 2, 3, 4, 5, 6, 6, 6, 6, 5, 4, 3, 2, 1, 1]
> >>>
>
> So there is one way of distributing 0 items to 3 bins; one way of
> distributing 1 item to 3 bins etc.  These are basically partition functions,
> but with constraints on the lengths (k) and maximum values (N-k).
>
> e.g. The partition function for 6, p(6) = 11 ,  i.e. = 6 = 5+1 = 4+2 = 4+1+1
> = 3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1.    But
> four of these partitions require more than 3 bins, another requires more
> than 5 items in a single bin.  So the result I'm looking for is 6.

Okay, I get it now.

> My code constructs a table s.t. table[i,j] contains the number of partitions
> of i of length j+1, p(i, j+1).  It uses the following relationship.
>
> p(n,k) = p(n-1, k-1) + p(n-k, k)
>
> The number of columns is restricted to k, so summing over the row indexed n
> gives me the number of partitions of length <= k.  Recursion arises because
> of the constraint on the bin sizes.  i.e.
>
> Let the maximum bin size be b, then for b<n,
>
> p(n;k,b) = sum(1 to k)p(n,k) - sum(i=0 to n-b-1)p(i;k-1,n-i)
>
> The cumulative table avoids some summing over table elements (well, at the
> first level of recursion anyway).  The dictionary is used to store
> intermediate results for reuse.  There are some obvious things I can do
> (like exploit the symmetry in the result), but I'd really like to get rid of
> the recursion.  Hope this makes the problem a bit clearer.  Thanks.

Clearer, yes. But definitely not easier.

I've been working on this problem since your message, and I haven't yet found
a way to do it iteratively with finesse. Brute force is a piece of cake; just
treat the max number of items per bin as the radix and the number of bins as
the number of digits in a number system, go from 0 to bins**maxperbin, and sum
it all up.

You'll have to wait a few days for the nice solution though. From a quick
overview I'd say that it deals with hyperdimensional equivalents of Pascal's
Triangle, so it's definitely ibu time...

-- 
Ignacio Vazquez-Abrams  <ignacio at openservices.net>