Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

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]

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]

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]

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]

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?

 

[castironpi]

Roy Smith wrote the following on 02/27/2008 06:56 PM:


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?

 

[castironpi]

Michael Robertson wrote the following on 02/27/2008 06:40 PM:


I found:

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

Do anyone know if there are better algorithms than this?

Or free?

 

[castironpi]

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?

 

[castironpi]

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]

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]

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]

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

That line should have been just:

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

of course.

Mark

 

[castironpi]

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.

 

[Michael Robertson]

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.

 

[castironpi]

(e-mail address removed) wrote the following on 02/27/2008 08:46 PM:


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.

 

[castironpi]

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

 

[castironpi]

Michael Robertson wrote the following on 02/27/2008 06:40 PM:



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?

 

[Michael Robertson]

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.

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.

 

[Mark Dickinson]

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

 

[Arnaud Delobelle]

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