I don't understand this recursive method in python to generate permutations

Question

How does this recursive method work to generate permutations given a string? Could someone explain me please?

def exchange(self, s):
    if 0 == len(s):
        yield s
    else:
        for i in range(len(s)):
            for p in self.exchange(s[:i] + s[i + 1:]):
                yield [s[i]] + p

It's called a ["generator"](https://wiki.python.org/moin/Generators) — rickdenhaan, Jul 28 '17 at 15:24
Relevant: https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python — MLavrentyev, Jul 28 '17 at 15:25
@rickdenhaan: I think that was clear. I think the OP has more problems with understanding the internal workings of the code. — Willem Van Onsem, Jul 28 '17 at 15:25

score 1 · Accepted Answer · answered Jul 28 '17 at 15:34

The code has the following idea: Deliver all permutations by choosing one element from the input and then deliver all permutations of the remaining elements, prepended by the chosen element. After this, repeat with another element.

So, if you have as input [0, 1, 2], then the code uses the first element (0) and builds all permutations of the remaining elements (1 and 2). (These permutations are [1, 2] and [2, 1] of course.)

Then it delivers (yields) the 0 prepended to [1, 2] and then the 0 prepended to [2, 1], i. e. [0, 1, 2] and [0, 2, 1].

Then it continues and chooses the next element (1). It then builds the permutations of the remaining elements (0, 2) (i. e. [0, 2] and [2, 0]).

And so forth.

I don't understand this recursive method in python to generate permutations

1 Answers1