Generating permutations using generators

Question

I was writing a program to generate all the permutations of a string:

def print_permutations_wrapper(str):
    strList = str.split()
    print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        print(strList)
        return

    print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    print_permutations_wrapper(str)


if __name__ == "__main__":
    main()

Its working correctly, but rather than printing it, I wanted to return it lazily using yield:

def print_permutations_wrapper(str):
    strList = str.split()
    yield from print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield strList
        return

    yield from print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        yield from print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    x = print_permutations_wrapper(str)
    print(list(x))

if __name__ == "__main__":
    main()

The output that I get is:

[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']]

rather than all the permutations.
How to correct this?

I am using Python 3.7.

You are mutating the same `strList`, thus the result will be a list of the same list. You can try to `yield list(strList)` in `print_permutations` to create a shallow copy of that list, or make use of the built-in [`itertools.permutations`](https://docs.python.org/3/library/itertools.html#itertools.permutations), which the documentation include example implementation. Also see related [“Least Astonishment” and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument). — metatoaster, Jun 07 '19 at 05:11
@metatoaster `yield list(strList)` yields a deep copy of that list, not a shallow copy. — Albin Paul, Jun 07 '19 at 05:16
Oh its working now.. thanks! You might want to write it in the answer. Interesting link. Definitely astonishing for a beginner! — Anmol Singh Jaggi, Jun 07 '19 at 05:21
@AlbinPaul `list` does not recursively duplicate any internal references that may be part of the list of references that it received from the argument. It only touches the top-level elements - you need [`deepcopy`](https://docs.python.org/3/library/copy.html#copy.deepcopy) for what you suggested. — metatoaster, Jun 07 '19 at 05:27

score 3 · Accepted Answer · answered Jun 07 '19 at 05:36

Taking your second program, but add a print(strList) will show that the generator function yielded what you expected, but the final output is clearly not what you expected. This is due to the fact that the program as structured takes a list, but does all the operation to this same copy (assumed to limit memory usage). You can also verify this by

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
True
>>> items[0] is strList
True

Clearly every single item inside the items are of the same original strList that got passed in. Given the simplicity of the problem, this may be avoided by yielding a shallow copy of the list instead. Thus the relevant yield part of the function will become

def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield list(strList)
        return

Now running it should produce:

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
False

Also, as an aside, permutation is in fact a part of the standard library, available via itertools.permutation.

Related: "Least Astonishment" and the Mutable Default Argument

Generating permutations using generators

1 Answers1