Re: recursive algorithm for balls in numbered boxes
Mark Dickinson-2 wrote: > > > This is a well-known trick: to divide 5 (unlabeled) balls amongst 3 > (labeled) boxes, you write down sequences of 5 o's and 2 x's, where > the o's represent the 5 balls and the 'x's represent dividers: > > ooxooxo -> [2, 2, 1] > xoooxoo -> [0, 3, 2] > > And 'combinations(7, 2)' yields successively all the possible > different placements for the 2 dividers in the 7 symbols. > > > This question seems to come up often enough (without the box size > limit twist) that maybe it would be useful to include something like > this recipe in the itertool documentation. > > > For getting this into itertools, I'd suggest opening a feature request > on bugs.python.org and assigning it to Raymond Hettinger. > > -- > Mark > -- > http://mail.python.org/mailman/listinfo/python-list > > You are correct--the case without capacity limits can be handled using the existing machinery in `itertools`. BTW--That trick with the dividers is discussed on page 38 of William Feller's classic text, "An Introduction to Probability Theory and Its Applications". As per your suggestion, I have opened a feature request and assigned it to Raymond. Thanks! -- View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32449079.html Sent from the Python - python-list mailing list archive at Nabble.com. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
Dr. Phillip M. Feldman wrote: > When I run my code, I get the same 14 configurations that your code > produces; I'm sorry, I ran the buggy code from http://old.nabble.com/file/p32439307/balls_in_numbered_boxes.py without realizing it was not http://old.nabble.com/file/p32440187/balls_in_numbered_boxes.py > the only different that I can see in the output is that the > configurations are produced in a different order. Note that your code is > not creating an iterator, so thus doesn't do what I want. The outer loop is in a generator expression and thus evaluates lazily. > Also, > generating the product set and then testing whether the total number of > balls is correct will potentially consider a huge number of cases that > must be rejected because the sum is wrong; this is too inefficient. Indeed; I should have added a disclaimer to make that clear. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
Chris, Your code is much cleaner than mine. I will have to figure out exactly how it is working. Thanks! Phillip -- View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32443579.html Sent from the Python - python-list mailing list archive at Nabble.com. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
Hello Peter, When I run my code, I get the same 14 configurations that your code produces; the only different that I can see in the output is that the configurations are produced in a different order. Note that your code is not creating an iterator, so thus doesn't do what I want. Also, generating the product set and then testing whether the total number of balls is correct will potentially consider a huge number of cases that must be rejected because the sum is wrong; this is too inefficient. Phillip In [2]: list(balls_in_numbered_boxes(10,[4,3,2,1,2])) Out[2]: [(4, 3, 2, 1, 0), (4, 3, 2, 0, 1), (4, 3, 1, 1, 1), (4, 3, 1, 0, 2), (4, 3, 0, 1, 2), (4, 2, 2, 1, 1), (4, 2, 2, 0, 2), (4, 2, 1, 1, 2), (4, 1, 2, 1, 2), (3, 3, 2, 1, 1), (3, 3, 2, 0, 2), (3, 3, 1, 1, 2), (3, 2, 2, 1, 2), (2, 3, 2, 1, 2)] -- View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32443548.html Sent from the Python - python-list mailing list archive at Nabble.com. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
On Sep 11, 1:43 am, "Dr. Phillip M. Feldman" wrote: > I've written a recursive class that creates an iterator to solve a general > formulation of the combinatorics problem known as "balls in numbered boxes" > (also known as "indistinguishable balls in distinguishable boxes"). The > code has been extensively tested and appears to work, but isn't terribly > elegant. Any suggestions about how to improve it will be appreciated. > > Also, I'd like to get this functionality into the Python's `itertools` > module (the present set of combinatorics functions in `itertools` does not > include "balls in boxes"). Does anyone know whom I should contact about > this? Note that for the version without size limits on individual boxes, the itertools.combination function already provides most of what's needed. For example: import itertools def balls_in_boxes(nballs, nboxes): n, k = nballs + nboxes - 1, nboxes - 1 for comb in itertools.combinations(range(n), k): yield [y - x - 1 for y, x in zip(comb + (n,), (-1,) + comb)] print "5 balls in 3 boxes" for combination in balls_in_boxes(5, 3): print combination assert len(combination) == 3 assert sum(combination) == 5 This is a well-known trick: to divide 5 (unlabeled) balls amongst 3 (labeled) boxes, you write down sequences of 5 o's and 2 x's, where the o's represent the 5 balls and the 'x's represent dividers: ooxooxo -> [2, 2, 1] xoooxoo -> [0, 3, 2] And 'combinations(7, 2)' yields successively all the possible different placements for the 2 dividers in the 7 symbols. This question seems to come up often enough (without the box size limit twist) that maybe it would be useful to include something like this recipe in the itertool documentation. For getting this into itertools, I'd suggest opening a feature request on bugs.python.org and assigning it to Raymond Hettinger. -- Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
Dr. Phillip M. Feldman wrote: > I've written a recursive class that creates an iterator to solve a general > formulation of the combinatorics problem known as "balls in numbered > boxes" > (also known as "indistinguishable balls in distinguishable boxes"). The > code has been extensively tested and appears to work, but isn't terribly > elegant. Any suggestions about how to improve it will be appreciated. Does the following do what you want? >>> from itertools import product >>> def binb(balls, boxsizes): ... return (fill for fill in product(*[range(bs+1) for bs in boxsizes]) if sum(fill) == balls) ... >>> for item in binb(10, [4, 3, 2, 1, 2]): ... print item ... (2, 3, 2, 1, 2) (3, 2, 2, 1, 2) (3, 3, 1, 1, 2) (3, 3, 2, 0, 2) (3, 3, 2, 1, 1) (4, 1, 2, 1, 2) (4, 2, 1, 1, 2) (4, 2, 2, 0, 2) (4, 2, 2, 1, 1) (4, 3, 0, 1, 2) (4, 3, 1, 0, 2) (4, 3, 1, 1, 1) (4, 3, 2, 0, 1) (4, 3, 2, 1, 0) If so, your implementation misses a few configurations: >>> from balls_in_numbered_boxes import balls_in_numbered_boxes as bb >>> for item in bb(10, [4, 3, 2, 1, 2]): ... print item ... [4 3 2 1 0] [3 3 2 1 1] [2 3 2 1 2] > Also, I'd like to get this functionality into the Python's `itertools` > module (the present set of combinatorics functions in `itertools` does not > include "balls in boxes"). Does anyone know whom I should contact about > this? Basically you have to convince Raymond Hettinger. I recommend that you post your suggestion on python-ideas for a general discussion rather than approaching him directly. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursive algorithm for balls in numbered boxes
On Sat, Sep 10, 2011 at 5:43 PM, Dr. Phillip M. Feldman wrote: > I've written a recursive class that creates an iterator to solve a general > formulation of the combinatorics problem known as "balls in numbered boxes" > (also known as "indistinguishable balls in distinguishable boxes"). The > code has been extensively tested and appears to work, but isn't terribly > elegant. Any suggestions about how to improve it will be appreciated. Significantly refactored (but untested) version: https://gist.github.com/1209079 Cheers, Chris -- http://rebertia.com -- http://mail.python.org/mailman/listinfo/python-list
recursive algorithm for balls in numbered boxes
I've written a recursive class that creates an iterator to solve a general formulation of the combinatorics problem known as "balls in numbered boxes" (also known as "indistinguishable balls in distinguishable boxes"). The code has been extensively tested and appears to work, but isn't terribly elegant. Any suggestions about how to improve it will be appreciated. Also, I'd like to get this functionality into the Python's `itertools` module (the present set of combinatorics functions in `itertools` does not include "balls in boxes"). Does anyone know whom I should contact about this? Phillip http://old.nabble.com/file/p32440187/balls_in_numbered_boxes.py balls_in_numbered_boxes.py -- View this message in context: http://old.nabble.com/recursive-algorithm-for-balls-in-numbered-boxes-tp32440187p32440187.html Sent from the Python - python-list mailing list archive at Nabble.com. -- http://mail.python.org/mailman/listinfo/python-list
