# Place n indistinguishable items into k distinguishable boxes

Discussion in 'Python' started by Michael Robertson, Feb 28, 2008.

1. ### Michael RobertsonGuest

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, Feb 28, 2008

2. ### Michael RobertsonGuest

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.

Michael Robertson, Feb 28, 2008

3. ### Roy SmithGuest

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, Feb 28, 2008
4. ### Michael RobertsonGuest

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, Feb 28, 2008
5. ### Michael RobertsonGuest

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?

Michael Robertson, Feb 28, 2008
6. ### Guest

On Feb 27, 9:03 pm, Michael Robertson <> 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?

, Feb 28, 2008
7. ### Guest

On Feb 27, 9:31 pm, Michael Robertson <> 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?

, Feb 28, 2008
8. ### Guest

On Feb 27, 8:40 pm, 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.

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

, Feb 28, 2008
9. ### Guest

On Feb 27, 10:12 pm, wrote:
> On Feb 27, 8:40 pm, 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.

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

, Feb 28, 2008
10. ### Michael RobertsonGuest

wrote the following on 02/27/2008 08:14 PM:
> On Feb 27, 10:12 pm, 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)

Michael Robertson, Feb 28, 2008
11. ### Mark DickinsonGuest

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]

Mark Dickinson, Feb 28, 2008
12. ### Mark DickinsonGuest

On Feb 27, 11:38 pm, Mark Dickinson <> wrote:
>             yield map(len, (''.join(s)).split('|'))

That line should have been just:

yield map(len, s.split('|'))

of course.

Mark

Mark Dickinson, Feb 28, 2008
13. ### Guest

On Feb 27, 10:41 pm, Mark Dickinson <> wrote:
> On Feb 27, 11:38 pm, Mark Dickinson <> wrote:
>
> >             yield map(len, (''.join(s)).split('|'))

>
> That line should have been just:
>
>             yield map(len, s.split('|'))
>
> of course.
>
> Mark

It's easier:

def rec( boxesleft, stonesleft, seq ):
if 1== boxesleft:
print( seq+ ( stonesleft, ) )
return
for i in range( stonesleft+ 1 ):
rec( boxesleft- 1, stonesleft- i, seq+ ( i, ) )
rec( 3, 4, () )
rec( 6, 1, () )
rec( 4, 2, () )

Just sort the list in text-ascending order, and it's pretty clear.

It uses tuple concat., which may be slower than Marks.

If you want an iterative, stay tuned.

, Feb 28, 2008
14. ### Michael RobertsonGuest

wrote the following on 02/27/2008 08:46 PM:
> Just sort the list in text-ascending order, and it's pretty clear.

Indeed. After trying Mark's solution, I saw that it sorted in a very
nice manner.

Michael Robertson, Feb 28, 2008
15. ### Guest

On Feb 27, 10:49 pm, Michael Robertson <>
wrote:
> wrote the following on 02/27/2008 08:46 PM:
>
> > Just sort the list in text-ascending order, and it's pretty clear.

>
> Indeed.  After trying Mark's solution, I saw that it sorted in a very
> nice manner.

You could also make it half-way through, then reverse it.

, Feb 28, 2008
16. ### Guest

On Feb 27, 10:46 pm, wrote:
> On Feb 27, 10:41 pm, Mark Dickinson <> wrote:
>
> > On Feb 27, 11:38 pm, Mark Dickinson <> wrote:

>
> > >             yield map(len, (''.join(s)).split('|'))

>
> > That line should have been just:

>
> >             yield map(len, s.split('|'))

>
> > of course.

>
> > Mark

>
> It's easier:
>
> def rec( boxesleft, stonesleft, seq ):
>         if 1== boxesleft:
>                 print( seq+ ( stonesleft, ) )
>                 return
>         for i in range( stonesleft+ 1 ):
>                 rec( boxesleft- 1, stonesleft- i, seq+ ( i, ) )
> rec( 3, 4, () )
> rec( 6, 1, () )
> rec( 4, 2, () )
>
> Just sort the list in text-ascending order, and it's pretty clear.
>
> It uses tuple concat., which may be slower than Marks.
>
> If you want an iterative, stay tuned.

for N, K in ( 4, 3 ), ( 1, 6 ), ( 2, 4 ), ( 6, 1 ):
if K== 1:
results= [ ( N, ) ]
else:
results= [ [ N- i, i ] for i in range( 0, N+ 1 ) ]
for j in range( K- 2 ):
news= []
for r in results:
for k in range( r[ 0 ]+ 1 ):
news.append( [ r[ 0 ]- k ]+ r[ 1: ]+ [ k ] )
results= news
news= []
for r in results:
news.append( tuple( r[ 1: ] )+ ( r[ 0 ], ) )
results= news
assert len( results )== len( set( results ) )
assert all( 0<= k<= N for r in results for k in r )
print( '%i/%i:'% ( N, K ),results )
print()

, Feb 28, 2008
17. ### Guest

On Feb 27, 8:47 pm, Michael Robertson <> 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?

, Feb 28, 2008
18. ### Michael RobertsonGuest

wrote the following on 02/28/2008 12:36 AM:
> On Feb 27, 8:47 pm, Michael Robertson <> 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.

Michael Robertson, Feb 28, 2008
19. ### Mark DickinsonGuest

On Feb 28, 5:02 am, Michael Robertson <> wrote:
> Thanks again for your efforts here.  This particular problem didn't
> appear in any course I took...certainly similar problems did.

And here's the obligatory not-very-obfuscated one-liner:

from itertools import combinations as c; boxings=lambda n,k[s[i
+1]+~s for i in range(k)] for s in [[-1]+list(t)+[n-~k] for t in
c(range(n-~k),k-1)])

You'll need to check out and compile the
latest svn sources to make it work, though.
And it doesn't work when k == 0.

Mark

Mark Dickinson, Feb 28, 2008
20. ### Arnaud DelobelleGuest

On Feb 28, 2:40 am, 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)

[...]

Here is my little function:

---------------
from itertools import chain
from operator import sub

def boxings(n, k):
"""boxings(n, k) -> iterator

Generate all ways to place n indistiguishable items into k
distinguishable boxes
"""
seq = [n] * (k-1)
while True:
yield map(sub, chain(seq, [n]), chain([0], seq))
for i, x in enumerate(seq):
if x:
seq[:i+1] = [x-1] * (i+1)
break
else:
return
---------------

It is purely iterative. I think it is not too wasteful but I haven't
tried to optimise it in any way.

In the function, 'seq' iterates over all increasing sequences of
length k-1 over {0,1,..n}.

Example:

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

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

... here is another attempt on the same principle:

---------------
def boxings(n, k):
"""boxings(n, k) -> iterator

Generate all ways to place n indistiguishable items into k
distinguishable boxes
"""
seq = [n]*k + [0]
while True:
yield tuple(seq - seq[i+1] for i in xrange(k))
i = seq.index(0) - 1
if i >= 1:
seq[i:k] = [seq - 1] * (k - i)
else:
return

--
Arnaud

Arnaud Delobelle, Feb 28, 2008