Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > recursive algorithm for balls in numbered boxes

Reply
Thread Tools

recursive algorithm for balls in numbered boxes

 
 
Dr. Phillip M. Feldman
Guest
Posts: n/a
 
      09-11-2011

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...bered_boxes.py
balls_in_numbered_boxes.py
--
View this message in context: http://old.nabble.com/recursive-algo...p32440187.html
Sent from the Python - python-list mailing list archive at Nabble.com.

 
Reply With Quote
 
 
 
 
Mark Dickinson
Guest
Posts: n/a
 
      09-11-2011
On Sep 11, 1:43*am, "Dr. Phillip M. Feldman"
<(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Dr. Phillip M. Feldman
Guest
Posts: n/a
 
      09-12-2011


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-algo...p32449079.html
Sent from the Python - python-list mailing list archive at Nabble.com.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Space between input boxes and selection boxes is not the same in Internet Explorer Stefan Mueller HTML 5 06-16-2009 02:06 PM
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Analysis of that "Dropping two glass balls from a building" puzzle. (WAS: analytical Skill for Java Development) Oliver Wong Java 1 04-05-2006 08:34 PM
4 balls: lone-ball side-bounce Xah Lee Java 6 03-06-2006 09:42 AM



Advertisments