recursive algorithm for balls in numbered boxes

Dr. Phillip M. Feldman Phillip.M.Feldman at gmail.com
Mon Sep 12 17:47:22 CEST 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-algorithm-for-balls-in-numbered-boxes-tp32440187p32449079.html
Sent from the Python - python-list mailing list archive at Nabble.com.




More information about the Python-list mailing list