D
Dr. Phillip M. Feldman
It is supposed to be possible to generate a list representation of any
iterator that produces a sequence of finite length, but this doesn't always
work. Here's a case where it does work:
Input:
from itertools import combinations
list(combinations(range(4),2))
Output:
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
When I define my own classes that produce iterators, conversion to a list
works for some of these classes but not for others. Here's a case where it
doesn't work:
In: list(balls_in_numbered_boxes(2, [3,3,3]))
Out:
[array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1])]
Note that if I apply the `next` method to the object, the output is correct:
In [5]: x=balls_in_numbered_boxes(3,[3,3,3])
In [6]: x.next()
Out[6]: array([3, 0, 0])
In [7]: x.next()
Out[7]: array([2, 1, 0])
In [8]: x.next()
Out[8]: array([1, 2, 0])
In [9]: x.next()
Out[9]: array([0, 3, 0])
In [10]: x.next()
Out[10]: array([0, 2, 1])
In [11]: x.next()
Out[11]: array([0, 1, 2])
In [12]: x.next()
Out[12]: array([0, 0, 3])
In [13]: x.next()
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
Code is attached (see below). Any suggestions as to what's going wrong will
be appreciated.
class balls_in_numbered_boxes(object):
"""
OVERVIEW
This class generates an iterator that produces all distinct distributions
of
indistinguishable balls among numbered boxes with specified capacity
limits.
(This is a generalization of the most common formulation of the problem,
where each box is sufficiently large to accommodate all of the balls, and
is
an important example of a class of combinatorics problems called 'weak
composition' problems).
CONSTRUCTOR INPUTS
n: the number of balls
limits: This argument is a list of length 1 or greater. The length of
the
list corresponds to the number of boxes. `limits` is a positive
integer
that specifies the maximum capacity of the ith box. If `limits`
equals
`n` (or greater), then the ith box can accommodate all `n` balls and thus
effectively has unlimited capacity.
"""
def __init__(self, n=None, limits=None):
if n < 0 or not isinstance(n,int):
raise BadInput("The number of balls n must be a non-negative
integer.")
if not isinstance(limits,list) or len(limits)<1:
raise BadInput("`limits` must be a non-empty list.")
for limit in limits:
if not isinstance(limit,int) or limit<1:
raise BadInput("Items in `limits` must be positive integers.")
# Copy constructor inputs to object attributes. We make a `deepcopy`
of
# `limits` to protect against the possibility of the calling program
# modifying it before all calls to the `next` method have been
completed.
self.n= n
self.limits= deepcopy(limits)
self.distribution= None
def __iter__(self):
return self
def next(self):
# If `self.distribution` is `None`, this is the initial call to
`next`,
# in which case we generate the initial distribution by assigning as
many
# balls as possible to the first box, as many balls that remain to the
# next box, and so on.
if self.distribution is None:
self.distribution= zeros(len(self.limits), dtype='i4')
balls= self.n
for box in xrange(len(self.limits)):
# Store as many balls as possible in the current box:
self.distribution[box]= min(balls,self.limits[box])
balls-= self.distribution[box]
if balls == 0: break
else:
# We fell through the above loop, which means that it was
impossible
# to distribute all of the balls:
raise BadInput("The total capacity of the boxes is less than the
"
"number of balls to be distributed.")
# Make first box the "current" box, i.e., the box from which a ball
# will be moved when the `next` method is invoked:
self.box= 0
return self.distribution
# `self.distribution` is not `None`, which means that this is not the
# initial invocation of `next`. We create the next distribution by
moving
# one ball to the right, unless this is impossible.
self.distribution[self.box]-= 1
for box in xrange(self.box+1,len(self.limits)):
# If this box is full, advance to the next one:
if self.distribution[box] == self.limits[box]: continue
self.distribution[box]+= 1
break
else:
# We fell through the above loop, which means that it was
impossible
# to find a new home for the ball that we were trying to move.
raise StopIteration
# If the current box--the box from which we have been removing balls--
is
# empty, advance to the next box:
if self.distribution[self.box] == 0: self.box+= 1
return self.distribution
iterator that produces a sequence of finite length, but this doesn't always
work. Here's a case where it does work:
Input:
from itertools import combinations
list(combinations(range(4),2))
Output:
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
When I define my own classes that produce iterators, conversion to a list
works for some of these classes but not for others. Here's a case where it
doesn't work:
In: list(balls_in_numbered_boxes(2, [3,3,3]))
Out:
[array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1]),
array([0, 0, 1])]
Note that if I apply the `next` method to the object, the output is correct:
In [5]: x=balls_in_numbered_boxes(3,[3,3,3])
In [6]: x.next()
Out[6]: array([3, 0, 0])
In [7]: x.next()
Out[7]: array([2, 1, 0])
In [8]: x.next()
Out[8]: array([1, 2, 0])
In [9]: x.next()
Out[9]: array([0, 3, 0])
In [10]: x.next()
Out[10]: array([0, 2, 1])
In [11]: x.next()
Out[11]: array([0, 1, 2])
In [12]: x.next()
Out[12]: array([0, 0, 3])
In [13]: x.next()
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
Code is attached (see below). Any suggestions as to what's going wrong will
be appreciated.
class balls_in_numbered_boxes(object):
"""
OVERVIEW
This class generates an iterator that produces all distinct distributions
of
indistinguishable balls among numbered boxes with specified capacity
limits.
(This is a generalization of the most common formulation of the problem,
where each box is sufficiently large to accommodate all of the balls, and
is
an important example of a class of combinatorics problems called 'weak
composition' problems).
CONSTRUCTOR INPUTS
n: the number of balls
limits: This argument is a list of length 1 or greater. The length of
the
list corresponds to the number of boxes. `limits` is a positive
integer
that specifies the maximum capacity of the ith box. If `limits`
equals
`n` (or greater), then the ith box can accommodate all `n` balls and thus
effectively has unlimited capacity.
"""
def __init__(self, n=None, limits=None):
if n < 0 or not isinstance(n,int):
raise BadInput("The number of balls n must be a non-negative
integer.")
if not isinstance(limits,list) or len(limits)<1:
raise BadInput("`limits` must be a non-empty list.")
for limit in limits:
if not isinstance(limit,int) or limit<1:
raise BadInput("Items in `limits` must be positive integers.")
# Copy constructor inputs to object attributes. We make a `deepcopy`
of
# `limits` to protect against the possibility of the calling program
# modifying it before all calls to the `next` method have been
completed.
self.n= n
self.limits= deepcopy(limits)
self.distribution= None
def __iter__(self):
return self
def next(self):
# If `self.distribution` is `None`, this is the initial call to
`next`,
# in which case we generate the initial distribution by assigning as
many
# balls as possible to the first box, as many balls that remain to the
# next box, and so on.
if self.distribution is None:
self.distribution= zeros(len(self.limits), dtype='i4')
balls= self.n
for box in xrange(len(self.limits)):
# Store as many balls as possible in the current box:
self.distribution[box]= min(balls,self.limits[box])
balls-= self.distribution[box]
if balls == 0: break
else:
# We fell through the above loop, which means that it was
impossible
# to distribute all of the balls:
raise BadInput("The total capacity of the boxes is less than the
"
"number of balls to be distributed.")
# Make first box the "current" box, i.e., the box from which a ball
# will be moved when the `next` method is invoked:
self.box= 0
return self.distribution
# `self.distribution` is not `None`, which means that this is not the
# initial invocation of `next`. We create the next distribution by
moving
# one ball to the right, unless this is impossible.
self.distribution[self.box]-= 1
for box in xrange(self.box+1,len(self.limits)):
# If this box is full, advance to the next one:
if self.distribution[box] == self.limits[box]: continue
self.distribution[box]+= 1
break
else:
# We fell through the above loop, which means that it was
impossible
# to find a new home for the ball that we were trying to move.
raise StopIteration
# If the current box--the box from which we have been removing balls--
is
# empty, advance to the next box:
if self.distribution[self.box] == 0: self.box+= 1
return self.distribution