Place n indistinguishable items into k distinguishable boxes

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

  1. 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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Michael Robertson

    Roy Smith Guest

    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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Michael Robertson

    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
    #6
  7. Michael Robertson

    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
    #7
  8. Michael Robertson

    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
    #8
  9. Michael Robertson

    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
    #9
  10. 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
    #10
  11. 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
    #11
  12. 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
    #12
  13. Michael Robertson

    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
    #13
  14. 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
    #14
  15. Michael Robertson

    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
    #15
  16. Michael Robertson

    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
    #16
  17. Michael Robertson

    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
    #17
  18. 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
    #18
  19. 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
    #19
  20. 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
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kay

    moving items between list boxes

    Kay, Feb 3, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    6,029
    =?Utf-8?B?QXZuZWVzaA==?=
    Feb 3, 2004
  2. Stefan Mueller
    Replies:
    5
    Views:
    12,415
    jamesxa
    Jun 16, 2009
  3. divya
    Replies:
    1
    Views:
    1,094
    Munna
    May 28, 2008
  4. Keefe Goldfisher via .NET 247

    Sizing text entry boxes on in-place editing of datagrid row with dynamically created columns

    Keefe Goldfisher via .NET 247, Mar 7, 2005, in forum: ASP .Net Datagrid Control
    Replies:
    0
    Views:
    184
    Keefe Goldfisher via .NET 247
    Mar 7, 2005
  5. ela
    Replies:
    12
    Views:
    355
    Uri Guttman
    Apr 6, 2009
Loading...

Share This Page