Python: calling list() on generator object produces incorrect result

Question

I was looking at the accepted solution to this question, which provides a Python implementation of an algorithm for producing unique permutations in lexicographic order. I have a somewhat shortened implementation:

def permutations(seq):
    seq = sorted(seq)
    while True:
        yield seq
        k = l = None
        for k in range(len(seq) - 1):
            if seq[k] < seq[k + 1]:
                l = k + 1
                break
        else:
            return

        (seq[k], seq[l]) = (seq[l], seq[k])
        seq[k + 1:] = seq[-1:k:-1]

What's really strange for me is that if I call list on the output of this function, I get wrong results. However, if I iterate over the results of this function one at a time, I get the expected results.

>>> list(permutations((1,2,1)))
[[2, 1, 1], [2, 1, 1], [2, 1, 1]]
>>> for p in permutations((1,2,1)):
...   print(p)
... 
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

^^^What the?! Another example:

>>> list(permutations((1,2,3)))
[[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]
>>> for p in permutations((1,2,3)):
...   print(p)
... 
[1, 2, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

And list comprehension also yields the incorrect values:

>>> [p for p in permutations((1,2,3))]
[[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]

I have no idea what's going on here! I've not seen this before. I can write other functions that use generators and I don't run into this:

>>> def seq(n):
...   for i in range(n):
...     yield i
... 
>>> list(seq(5))
[0, 1, 2, 3, 4]

What's going on in my example above that causes this?

@StephenRauch Well, I certainly *didn't* expect different behavior depending on whether I iterate the result or call `list`. — JawguyChooser, Feb 16 '18 at 06:35
*Aside*: Why do you have `k = None` and `l = None`? If you remove them, you should get the same behavior. — Robᵩ, Feb 16 '18 at 06:56
if `k` and `l` aren't declared outside of the for loop then they wouldn't be around when I try to mutate `seq` below. — JawguyChooser, Feb 16 '18 at 06:58
I don't think that's true. Index variables in `for` loops are visible in the enclosing scope in both Python2 and Python3. See, for example, https://eli.thegreenplace.net/2015/the-scope-of-index-variables-in-pythons-for-loops/ or https://docs.python.org/dev/reference/compound_stmts.html#the-for-statement or just delete the line and see that it still works. — Robᵩ, Feb 16 '18 at 07:04

juanpa.arrivillaga · Accepted Answer · 2018-02-16T06:48:01.547

You modify seq within the generator, after you've yielded it. You keep yielding the same object, and modifying it.

    (seq[k], seq[l]) = (seq[l], seq[k]) # this mutates seq
    seq[k + 1:] = seq[-1:k:-1] # this mutates seq

Note, your list contains the same object multiple times:

In [2]: ps = list(permutations((1,2,1)))

In [3]: ps
Out[3]: [[2, 1, 1], [2, 1, 1], [2, 1, 1]]

In [4]: [hex(id(p)) for p in ps]
Out[4]: ['0x105cb3b48', '0x105cb3b48', '0x105cb3b48']

So, try yielding a copy:

def permutations(seq):
    seq = sorted(seq)
    while True:
        yield seq.copy()
        k = None
        l = None
        for k in range(len(seq) - 1):
            if seq[k] < seq[k + 1]:
                l = k + 1
                break
        else:
            return

        (seq[k], seq[l]) = (seq[l], seq[k])
        seq[k + 1:] = seq[-1:k:-1]

And, voila:

In [5]: def permutations(seq):
   ...:     seq = sorted(seq)
   ...:     while True:
   ...:         yield seq.copy()
   ...:         k = None
   ...:         l = None
   ...:         for k in range(len(seq) - 1):
   ...:             if seq[k] < seq[k + 1]:
   ...:                 l = k + 1
   ...:                 break
   ...:         else:
   ...:             return
   ...:
   ...:         (seq[k], seq[l]) = (seq[l], seq[k])
   ...:         seq[k + 1:] = seq[-1:k:-1]
   ...:

In [6]: ps = list(permutations((1,2,1)))

In [7]: ps
Out[7]: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

As to why printing in a for-loop doesn't reveal this behavior, it's because at that moment in the iteration seq has the "correct" value, so consider:

In [10]: result = []
    ...: for i, x in enumerate(permutations((1,2,1))):
    ...:     print("iteration ", i)
    ...:     print(x)
    ...:     result.append(x)
    ...:     print(result)
    ...:
iteration  0
[1, 1, 2]
[[1, 1, 2]]
iteration  1
[1, 2, 1]
[[1, 2, 1], [1, 2, 1]]
iteration  2
[2, 1, 1]
[[2, 1, 1], [2, 1, 1], [2, 1, 1]]

Aha, yes, okay, I believe I understand that explanation of why I was getting the same item back again and again. Thanks! What's still a little unclear to me is why I get a different result when I use a `for p in permuatations(seq): print(p)` idiom. — JawguyChooser, Feb 16 '18 at 06:36
@JawguyChooser because that is *printing the seq* at that moment. You don't modify it until `next` is called on the generator (implicitly in the for-loop).` If you did something like `result = []` then `for x in permutations(...): print(x); result.append(x); print(result)` it should become clear what is happening. — juanpa.arrivillaga, Feb 16 '18 at 06:38
Aha, I think I follow. That's an interesting subtlety Thanks for the prompt and clear answer! — JawguyChooser, Feb 16 '18 at 06:41
@JawguyChooser added the example. As an aside, you should read this: https://nedbatchelder.com/text/names.html about how python variables work. Once you grok it, what's going on should be totally obvious. — juanpa.arrivillaga, Feb 16 '18 at 06:43
Yes, thank you, I have run across this in the past, somehow the generator context here threw me off. And your example with that result array that seems to change with each iteration of the loop is really quite stunning! — JawguyChooser, Feb 16 '18 at 06:51

Python: calling list() on generator object produces incorrect result

1 Answers1