funny generator behaviour

[Edvin Fuglebakk]

I have written a generator that puzzles me:

The generator is supposed to create ordered selections of a set of
objects. repetition of objects is allowed and the selections should be
of a size determined by a pramter to the generator.

Now, if I try to accummulate the generated selections into a list I get
some peculiar behaviour that I hope maybe some of you can help me
understand:

Help much appreciated
-Edvin

#straightforward acumulation. Does not give the expected result

>>> d=[]
>>> for f in orderedCombinations([1,2],3):

.... d.append(f)
....[[1], [2], [1], [2], [1], [2], [1], [2]]

#accumulating shallow copies of the genereated combinations works:

>>> d=[]
>>> for f in orderedCombinations([1,2],3):

.... d.append(f[:])
....[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2,
2, 1], [2, 2, 2]]


#The generator:
def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition from
pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):

#insert and pop to avoid copying entire list
combo.insert(0,m)
yield combo
combo.pop(0)

 

[pruebauno]

I have written a generator that puzzles me:

The generator is supposed to create ordered selections of a set of
objects. repetition of objects is allowed and the selections should be
of a size determined by a pramter to the generator.

Now, if I try to accummulate the generated selections into a list I get
some peculiar behaviour that I hope maybe some of you can help me
understand:

Help much appreciated
-Edvin

#straightforward acumulation. Does not give the expected result

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f)
...[[1], [2], [1], [2], [1], [2], [1], [2]]

#accumulating shallow copies of the genereated combinations works:

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f[:])
...[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2,
2, 1], [2, 2, 2]]

#The generator:
def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition from
pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):

#insert and pop to avoid copying entire list
combo.insert(0,m)
yield combo
combo.pop(0)

Functional style (like the recursion you are using) and mutable
datastructures are hard to reason about. This version works for me:

def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition
from
pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):
yield [m]+combo

 

[Aaron Brady]

def orderedCombinations(pool, k):
    """
    Generator yielding ordered selections of size k with repetition from
pool.
    """

    if k == 1:
        for m in pool:
            yield [m]

    if k > 1:

        for m in pool:
            for combo in orderedCombinations(pool, k-1):

                #insert and pop to avoid copying entire list
                combo.insert(0,m)
                yield combo
                combo.pop(0)

'combo.pop' is the problem. When the caller saves the iteration
variable, the generator modifies it on the next call.

a= []
b= [0]
a.append( b )
a [[0]]
b.insert( 0, 1 )
a

[[1, 0]]

If you want your output to have X lists, you need to create X lists.
Perhaps copy is not the most efficient, but you can't have one list
try do be X different lists when viewed from different angles. Though
that would be cool.

 

[pruebauno]

I have written a generator that puzzles me:

The generator is supposed to create ordered selections of a set of
objects. repetition of objects is allowed and the selections should be
of a size determined by a pramter to the generator.

Now, if I try to accummulate the generated selections into a list I get
some peculiar behaviour that I hope maybe some of you can help me
understand:

Help much appreciated
-Edvin

#straightforward acumulation. Does not give the expected result

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f)
...[[1], [2], [1], [2], [1], [2], [1], [2]]

#accumulating shallow copies of the genereated combinations works:

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f[:])
...[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2,
2, 1], [2, 2, 2]]

#The generator:
def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition from
pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):

#insert and pop to avoid copying entire list
combo.insert(0,m)
yield combo
combo.pop(0)

BTW if you search in the fine manual version 2.6 you will find that a
slick implementation is already part of the standard library (hint:
itertools):

def orderedCombinations(pool, k):
result = [[]]
for poolel in [pool] * k:
result = [x+[y] for x in result for y in poolel]
return result

 

[pruebauno]

I have written a generator that puzzles me:

The generator is supposed to create ordered selections of a set of
objects. repetition of objects is allowed and the selections should be
of a size determined by a pramter to the generator.

Now, if I try to accummulate the generated selections into a list I get
some peculiar behaviour that I hope maybe some of you can help me
understand:

Help much appreciated
-Edvin

#straightforward acumulation. Does not give the expected result

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f)
...[[1], [2], [1], [2], [1], [2], [1], [2]]

#accumulating shallow copies of the genereated combinations works:

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f[:])
...[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2,
2, 1], [2, 2, 2]]

#The generator:
def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition from
pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):

#insert and pop to avoid copying entire list
combo.insert(0,m)
yield combo
combo.pop(0)

def orderedCombinations(pool, k):
res=[[]]
for i in xrange(k):
res=[n+[m] for n in res for m in pool]
return res

 

[Arnaud Delobelle]

I have written a generator that puzzles me:

The generator is supposed to create ordered selections of a set of
objects. repetition of objects is allowed and the selections should be
of a size determined by a pramter to the generator.

Now, if I try to accummulate the generated selections into a list I
get some peculiar behaviour that I hope maybe some of you can help me
understand:

Help much appreciated
-Edvin

#straightforward acumulation. Does not give the expected result

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f)
...[[1], [2], [1], [2], [1], [2], [1], [2]]

#accumulating shallow copies of the genereated combinations works:

d=[]
for f in orderedCombinations([1,2],3):

... d.append(f[:])
...[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2,
2, 1], [2, 2, 2]]


#The generator:
def orderedCombinations(pool, k):
"""
Generator yielding ordered selections of size k with repetition
from pool.
"""

if k == 1:
for m in pool:
yield [m]

if k > 1:

for m in pool:
for combo in orderedCombinations(pool, k-1):

#insert and pop to avoid copying entire list
combo.insert(0,m)
yield combo

I haven't tried your code but I think the problem is that you yield a
list above and then mutate it below, so when you generate the next
combination the previous one is mutated. Change the above line to

yield list(combo)

and it should sort the problem.