Removing Recursion

[Duncan Smith]

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.

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.

Duncan Smith