«

Hi,

I need a generator which produces all ways to place n indistinguishable
items into k distinguishable boxes.

For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.

(0,0,4)
(0,4,0)
(4,0,0)

(0,2,2)
(2,0,2)
(2,2,0)

(0,1,3)
(0,3,1)
(3,0,1)
(3,1,0)

(1,1,2)
(1,2,1)
(2,1,1)

The generator needs to be fast and efficient.

Thanks.

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:

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

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

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.

In article <fq56vu$aue$>,
Michael Robertson <> wrote:

> Hi,
>
> I need a generator which produces all ways to place n indistinguishable
> items into k distinguishable boxes.
>
> For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
> (0,0,4)
> (0,4,0)
> (4,0,0)
>
> (0,2,2)
> (2,0,2)
> (2,2,0)
>
> (0,1,3)
> (0,3,1)
> (3,0,1)
> (3,1,0)
>
> (1,1,2)
> (1,2,1)
> (2,1,1)
>
> The generator needs to be fast and efficient.
>
> Thanks.

What course is this homework problem for?

Roy Smith wrote the following on 02/27/2008 06:56 PM:
> What course is this homework problem for?

None. I assume you have an answer to this *trivial* problem...

It's actually a very general question relating to a very specific
problem I am working on. Normally, I do not reply to such snide
remarks, but I'd like to note that this post would never have been made
if there *were* a Python package which provided these common
combinatorial methods.

Michael Robertson wrote the following on 02/27/2008 06:40 PM:
> I need a generator which produces all ways to place n indistinguishable
> items into k distinguishable boxes.

I found:

http://portal.acm.org/citation.cfm?doid=363347.363390

Do anyone know if there are better algorithms than this?

On Feb 27, 9:03*pm, Michael Robertson <mcrobert...@hotmail.com> wrote:
> Roy Smith wrote the following on 02/27/2008 06:56 PM:
>
> > What course is this homework problem for?
>
> None. *I assume you have an answer to this *trivial* problem...
>
> It's actually a very general question relating to a very specific
> problem I am working on. *Normally, I do not reply to such snide
> remarks, but I'd like to note that this post would never have been made
> if there *were* a Python package which provided these common
> combinatorial methods.

Sounds fun. Do I have class in the morning?

On Feb 27, 9:31*pm, Michael Robertson <mcrobert...@hotmail.com> wrote:
> Michael Robertson wrote the following on 02/27/2008 06:40 PM:
>
> > I need a generator which produces all ways to place n indistinguishable
> > items into k distinguishable boxes.
>
> I found:
>
> http://portal.acm.org/citation.cfm?doid=363347.363390
>
> Do anyone know if there are better algorithms than this?

Or free?

On Feb 27, 8:40*pm, Michael Robertson <mcrobert...@hotmail.com> wrote:
> Hi,
>
> I need a generator which produces all ways to place n indistinguishable
> items into k distinguishable boxes.
>
> For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
> (0,0,4)
> (0,4,0)
> (4,0,0)
>
> (0,2,2)
> (2,0,2)
> (2,2,0)
>
> (0,1,3)
> (0,3,1)
> (3,0,1)
> (3,1,0)
>
> (1,1,2)
> (1,2,1)
> (2,1,1)
>
> The generator needs to be fast and efficient.
>
> Thanks.

Note that the boxes are indistinguishable, and as such, ( 1, 0, 3 ) ==
( 3, 0, 1 ), but != ( 3, 1, 0 ). How so?

On Feb 27, 10:12*pm, castiro...@gmail.com wrote:
> On Feb 27, 8:40*pm, Michael Robertson <mcrobert...@hotmail.com> wrote:
>
>
>
>
>
> > Hi,
>
> > I need a generator which produces all ways to place n indistinguishable
> > items into k distinguishable boxes.
>
> > For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
> > (0,0,4)
> > (0,4,0)
> > (4,0,0)
>
> > (0,2,2)
> > (2,0,2)
> > (2,2,0)
>
> > (0,1,3)
> > (0,3,1)
> > (3,0,1)
> > (3,1,0)
>
> > (1,1,2)
> > (1,2,1)
> > (2,1,1)
>
> > The generator needs to be fast and efficient.
>
> > Thanks.
>
> Note that the boxes are indistinguishable, and as such, ( 1, 0, 3 ) ==
> ( 3, 0, 1 ), but != ( 3, 1, 0 ). *How so?- Hide quoted text -
>
> - Show quoted text -

Ah, correction, retracted. -disting-uishable boxes. Copy, but then,
where's ( 1, 0, 3 )?

wrote the following on 02/27/2008 08:14 PM:
> On Feb 27, 10:12 pm, castiro...@gmail.com wrote:
>>> For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.

>>> (0,0,4)
>>> (0,4,0)
>>> (4,0,0)
>>> (0,2,2)
>>> (2,0,2)
>>> (2,2,0)
>>> (0,1,3)
>>> (0,3,1)
>>> (3,0,1)
>>> (3,1,0)
>>> (1,1,2)
>>> (1,2,1)
>>> (2,1,1)
>
> Ah, correction, retracted. -disting-uishable boxes. Copy, but then,
> where's ( 1, 0, 3 )?

I only listed 13 ways...sorry about that. Missing are:

(1, 0, 3) and (1, 3, 0)