can't generate iterator from list

  • Thread starter Dr. Phillip M. Feldman
  • Start date
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
 
M

Miki Tebeka

1. Can you post the code somewhere where it's indented properly? (http://paste.pocoo.org/)
2. In the list example you call balls_in_numbered_boxes(2, [3,3,3]) but in the interactive example you call balls_in_numbered_boxes(3,[3,3,3])
 
M

Miki Tebeka

1. Can you post the code somewhere where it's indented properly? (http://paste.pocoo.org/)
2. In the list example you call balls_in_numbered_boxes(2, [3,3,3]) but in the interactive example you call balls_in_numbered_boxes(3,[3,3,3])
 
S

Steven D'Aprano

Dr. Phillip M. Feldman said:
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])]


But it does work -- it generates a list, exactly as expected.

The problem is not that you can't generate a list. The problem is that the
list you generate is not what you expect.

What you have here is a list containing the same array, repeated three
times. When you print the permutations one at a time, you don't notice, but
by collecting them all at once, you see clearly that they are the same
array object. Try this:

combos = list(balls_in_numbered_boxes(2, [3,3,3]))
[id(a) for a in combos]


I expect you will see something like [123456, 123456, 123456].


The simplest fix is to fix the next() method so that it returns a copy of
self.distribution instead of the array itself.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top