Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

castironpi at gmail.com wrote the following on 02/28/2008 12:36 AM:
> On Feb 27, 8:47 pm, Michael Robertson <mcrobert... at hotmail.com> wrote:
> Your only casualty here is all the zeroes in (4,0,0,..).  You don't
> want to swap k_2 and k_3 in (4,0,0).  (Is that what permutation
> means?)

Correct.  Though by 'permutation', I meant 'permutations with 
repetitions'---so the algorithm would have handled that.

> 
>> In addition to having to generate permutations for each integer
>> partition, I'd have to ignore all integer partitions which had more than
>> k parts...this seemed like a bad way to go (bad as in horribly inefficient).
>>
>> Better ideas are appreciated.
> 
> Running time on my recursive was K** 2* N, counting the copy, I
> think.  sum( 1..i )== i( i+ 1 )/ 2, O( i** 2 ).  My iterative was
> slower, K** 3* N, unless you save a K or N in the small length of K
> early on, I think.  Did anyone take this course that can tell me?

Thanks again for your efforts here.  This particular problem didn't 
appear in any course I took...certainly similar problems did.