Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Place n indistinguishable items into k distinguishable boxes

Reply
Thread Tools

Place n indistinguishable items into k distinguishable boxes

 
 
Michael Robertson
Guest
Posts: n/a
 
      02-28-2008
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.
 
Reply With Quote
 
 
 
 
Michael Robertson
Guest
Posts: n/a
 
      02-28-2008
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.
 
Reply With Quote
 
 
 
 
Roy Smith
Guest
Posts: n/a
 
      02-28-2008
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?
 
Reply With Quote
 
Michael Robertson
Guest
Posts: n/a
 
      02-28-2008
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.
 
Reply With Quote
 
Michael Robertson
Guest
Posts: n/a
 
      02-28-2008
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?
 
Reply With Quote
 
castironpi@gmail.com
Guest
Posts: n/a
 
      02-28-2008
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?
 
Reply With Quote
 
castironpi@gmail.com
Guest
Posts: n/a
 
      02-28-2008
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?
 
Reply With Quote
 
castironpi@gmail.com
Guest
Posts: n/a
 
      02-28-2008
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?
 
Reply With Quote
 
castironpi@gmail.com
Guest
Posts: n/a
 
      02-28-2008
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 )?
 
Reply With Quote
 
Michael Robertson
Guest
Posts: n/a
 
      02-28-2008
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)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Space between input boxes and selection boxes is not the same in Internet Explorer Stefan Mueller HTML 5 06-16-2009 02:06 PM
resolve single line with multiple items into mutliple lines, single items ela Perl Misc 12 04-06-2009 06:47 PM
Taskbar - Past Items back into Current Items Moke Gibboni Computer Support 5 10-29-2008 05:26 PM
unable to retrieve listbox items on postback , items moved usingjavascript between 2 list boxes (source and target ) divya ASP .Net 1 05-28-2008 05:27 AM
help, black dogs face indistinguishable lucky1 Digital Photography 22 03-25-2005 12:00 AM



Advertisments
 



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57