Place n indistinguishable items into k distinguishable boxes

[castironpi at gmail.com]

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