[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

Place n indistinguishable items into k distinguishable boxes

Michael Robertson

2/28/2008 2:40:00 AM

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

Michael Robertson

2/28/2008 2:47:00 AM

0

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.

Roy Smith

2/28/2008 2:56:00 AM

0

In article <fq56vu$aue$1@skeeter.ucdavis.edu>,
Michael Robertson <mcrobertson@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.

What course is this homework problem for?

Michael Robertson

2/28/2008 3:03:00 AM

0

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

2/28/2008 3:31:00 AM

0

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

Do anyone know if there are better algorithms than this?

Aaron Brady

2/28/2008 3:32:00 AM

0

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?

Aaron Brady

2/28/2008 4:03:00 AM

0

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=363...
>
> Do anyone know if there are better algorithms than this?

Or free?

Aaron Brady

2/28/2008 4:13:00 AM

0

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?

Aaron Brady

2/28/2008 4:14:00 AM

0

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

Michael Robertson

2/28/2008 4:34:00 AM

0

castironpi@gmail.com 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)

Mark Dickinson

2/28/2008 4:39:00 AM

0

Here's a possible solution. I'm sure others will comment on how to
fix up its inefficiencies (like the potentially slow string
concatenations...).



def comb(n, k):
if n == k == 0:
yield ''
else:
if n > 0:
for x in comb(n-1, k):
yield ' ' + x
if k > 0:
for x in comb(n, k-1):
yield '|' + x

def boxings(n, k):
if k == 0:
if n == 0:
yield []
else:
for s in comb(n, k-1):
yield map(len, (''.join(s)).split('|'))

for b in boxings(4, 3):
print b


Output:

[4, 0, 0]
[3, 1, 0]
[3, 0, 1]
[2, 2, 0]
[2, 1, 1]
[2, 0, 2]
[1, 3, 0]
[1, 2, 1]
[1, 1, 2]
[1, 0, 3]
[0, 4, 0]
[0, 3, 1]
[0, 2, 2]
[0, 1, 3]
[0, 0, 4]