Place n indistinguishable items into k distinguishable boxes

[castironpi at gmail.com]

On Feb 27, 8:47 pm, Michael Robertson <mcrobert... at hotmail.com> wrote:
> Michael Robertson wrote the following on 02/27/2008 06:40 PM:
>
> > Hi,
>
> > I need a generator which produces all ways to place n indistinguishable
> > items into k distinguishable boxes.
>
> My first thought was to generate all integer partitions of n, and then
> generate all permutations on k elements.  So:

Two more cents:

> 4 = 4
>    = 3 + 1
>    = 2 + 2
>    = 2 + 1 + 1

And if |x|> k, discard it.  For k= 1, you'd stop after 4 = 4.  <Reads
below.>  Ah, you said that.  Also make sure you stop at floor( k/ 2 ),
so you don't get 4 = 1 + 3.

> Then for 4,  generate all permutations of x=(4,0,0,..),  |x|=k
> Then for 3,1 generate all permutations of x=(3,1,0,..),  |x|=k
> Then for 2,2 generate all permutations of x=(2,2,0...),  |x|=k
> ...

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?)

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