Place n indistinguishable items into k distinguishable boxes
Michael Robertson
mcrobertson at hotmail.com
Thu Feb 28 11:02:14 CET 2008
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.
More information about the Python-list
mailing list