On Feb 28, 2:40 am, Michael Robertson <[EMAIL PROTECTED]> 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[i] - seq[i+1] for i in xrange(k))
i = seq.index(0) - 1
if i >= 1:
seq[i:k] = [seq[i] - 1] * (k - i)
else:
return
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
