Place n indistinguishable items into k distinguishable boxes
Michael Robertson
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
> 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
Michael Robertson <mcrob...@hotmail.com> wrote:
What course is this homework problem for?
Michael Robertson
> 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
> 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?
casti...@gmail.com
Sounds fun. Do I have class in the morning?
casti...@gmail.com
Or free?
casti...@gmail.com
Note that the boxes are indistinguishable, and as such, ( 1, 0, 3 ) ==
( 3, 0, 1 ), but != ( 3, 1, 0 ). How so?
casti...@gmail.com
>
> - Show quoted text -
Ah, correction, retracted. -disting-uishable boxes. Copy, but then,
where's ( 1, 0, 3 )?
Michael Robertson
> 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
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
casti...@gmail.com
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.
casti...@gmail.com
wrote:
You could also make it half-way through, then reverse it.
casti...@gmail.com
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()
casti...@gmail.com
> 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?
Michael Robertson
> On Feb 27, 8:47 pm, Michael Robertson <mcrobert...@hotmail.com> 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.
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[i] 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:
>>> 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[i] - seq[i+1] for i in xrange(k))
i = seq.index(0) - 1
if i >= 1:
seq[i:k] = [seq[i] - 1] * (k - i)
else:
return
--
Arnaud
Arnaud Delobelle
> ... 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[i] - seq[i+1] for i in xrange(k))
> i = seq.index(0) - 1
> if i >= 1:
> seq[i:k] = [seq[i] - 1] * (k - i)
> else:
> return
Actually this is better as it handles k=0 correctly:
def boxings(n, k):
seq, i = [n]*k + [0], k
while i:
yield tuple(seq[i] - seq[i+1] for i in xrange(k))
i = seq.index(0) - 1
seq[i:k] = [seq[i] - 1] * (k-i)
--
Arnaud
casti...@gmail.com
> On Feb 28, 5:02 am, Michael Robertson <mcrobert...@hotmail.com> 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[i] for i in range(k)] for s in [[-1]+list(t)+[n-~k] for t in
> c(range(n-~k),k-1)])
This calls for an obfuscation metric, several books, and two personal
references. What is ~k doing in there twice?
(Aside: throw in an obligatority one too. Sigh.)