«

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]

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

That line should have been just:

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

of course.

Mark

On Feb 27, 10:41*pm, Mark Dickinson <dicki...@gmail.com> wrote:
> On Feb 27, 11:38*pm, Mark Dickinson <dicki...@gmail.com> 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.

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.

On Feb 27, 10:49*pm, Michael Robertson <mcrobert...@hotmail.com>
wrote:
> castiro...@gmail.com 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.

On Feb 27, 10:46*pm, castiro...@gmail.com wrote:
> On Feb 27, 10:41*pm, Mark Dickinson <dicki...@gmail.com> wrote:
>
> > On Feb 27, 11:38*pm, Mark Dickinson <dicki...@gmail.com> 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()

On Feb 27, 8:47*pm, Michael Robertson <mcrobert...@hotmail.com> 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?

wrote the following on 02/28/2008 12:36 AM:
> 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.

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

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

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

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