Removing Recursion

[Duncan Smith]

"Ignacio Vazquez-Abrams" <ignacio at openservices.net> wrote in message
news:mailman.1001360367.28072.python-list at python.org...
> 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.
>

Yes, it took me a little while just to get something that worked.  But that
was (at least partly) because I started writing the code before checking my
maths.

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

Yes, finding a 'good' algorithm looks difficult.  If I have any flashes of
brilliance (you never know?) and come up with something I'll post it here.
A closed form expression would be nice, but I'm pretty sure there isn't
one.:-)

Duncan

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