0

I am trying to understand the "yield".

First, the code that I can't understand is below.

def permutations(seq):
    if len(seq) <= 1: yield seq
    else:
        for perm in permutations(seq[1:]):
            for i in range(len(perm)+1):
                yield perm[i:] + seq[0:1] + perm[:i]

print list(permutations(['police', 'buffalo', 'fish']))

The result is as below:

[['fish', 'buffalo', 'police'], ['buffalo', 'police', 'fish'], ['police', 'fish', 'buffalo'], ['buffalo', 'fish', 'police'], ['fish', 'police', 'buffalo'], ['police', 'buffalo', 'fish']]

My undertanding level about "yield" is just it is used for generater. And I can understand the code below. 

def reverse(data):
    for index in range(len(data) -1, -1, -1):
        yield data[index]

for char in reverse('golf'):
    print(char)

f
l
o
g

My level is just understanding above.. but with recursion, I can't understand... please explain. Thanks

GoodGJ
  • 339
  • 1
  • 4
  • 17
  • Possible duplicate [The Python yield keyword explained](http://stackoverflow.com/q/231767/1982962) – Kobi K Apr 28 '14 at 14:02
  • @KobiK the OP is asking specificaly about how `yield` works in a recursive function. – Adrian Ratnapala Apr 28 '14 at 14:19
  • @Adrian Ratnapala, actually you are right since yield does not work the same way in recursive functions. – Kobi K Apr 28 '14 at 14:24
  • 1
    @KobiK depending on you point of view, it does work the same way. It *doesn't* yield a result to the ultimate consumer, only to the immediate caller -- just like any other generator. – Adrian Ratnapala Apr 28 '14 at 16:06

2 Answers2

3

Yes, yield is for generators. That implies that when called, they return iterators. Generators can be recursive: they will call themselves, get an iterator and the iterate over it, on each Iteration they can yield up as many or few of their own elements as they like.

In your example permutations is a generator which always returns an iterator over lists.

if len(seq) <= 1: yield seq

Is simple enough: in the trivial case, just generate one list, seq itself.

for perm in permutations(seq[1:]):
        ...

Means "now iterate over different sequence-of-lists", in this case that is the sequence of all permutations of the elements after the first. In each iteration we have a nested loop that inserts the first element into each position of the permutation and yields the result.

I hope that helps. It's a little hard for me because I don't know exactly what you are confused about.

Update: the OP wants to know why the first result is in reverse order. Consider the line:

yield perm[i:] + seq[0:1] + perm[:i]

For the first result (i=0) this is equivalent to yield perm + seq[0:1] -- the first element is sent to the end of the yielded list. By induction, this result is the reverse of seq. If you want the first result to be ['police', 'buffalo', 'fish'] then you can do:

yield perm[:i] + seq[0:1] + perm[i:]
Adrian Ratnapala
  • 5,485
  • 2
  • 29
  • 39
  • Thanks for answering. What I can't understand is why the result is starting with '['fish', 'buffalo', 'police']'. Maybe I think I can't understand the recursive structure of permutation function.. – GoodGJ Apr 28 '14 at 14:30
  • @GoodGJ I don't think that has much to do with the recursion. It's just the way the results are constructed, see my update for details. – Adrian Ratnapala Apr 28 '14 at 16:02
1

The code you've given works according to this algorithm:

  1. If the sequence has one item or is empty, the only permutation is the sequence itself
  2. Separate the sequence into its first element, and the list of all its remaining elements
  3. Consider all the permutations of the remainder of the sequence, according to this same algorithm. For each permutation:
    1. For each position in the permutation:
      1. Split the permutation at that position
      2. Insert the first element of the original sequence in that split. This is a new permutation of the original sequence.
  4. Done.

The original code is slightly strange in how it achieves point 3.1.2. We can make it this a little bit clearer by using more variables to show the relationship to the algorithm more clearly - this assumes you're using Python 3:

def permutations(seq):
    if len(seq) <= 1: 
        yield seq 
    else:
        first, *rest = seq
        for perm in permutations(rest):
            for i in range(len(perm)+1):
                before = perm[:i]
                after = perm[i:]
                yield after + [first] + before

As you can see, the final line switches the start and end of the permutation for no real reason. It could just as easily do before + [first] + after, but the author decided not to. This doesn't affect how the algorithm works - it will find all the orderings, including the mirrored ones - but it means the order it produces them in might be a little strange.

You can use a similar recursive generator to implement reverse as well. In this case, the algorithm is:

  1. If the sequence only has one item or is empty, it is its own reverse
  2. Split the sequence into its first element and the list of all remaining elements
  3. Use this algorithm to reverse the remaining elements
  4. Yield each item of the result of the last step
  5. Yield the first element of the original sequence

In Python, it looks like this:

def reverse(seq): if len(seq) <= 1: return seq

  first, *rest = seq
  for item in reverse(rest):
       yield item
  # Or you could use:
  #  yield from reverse(rest)
  # Instead of the above loop
  yield first
lvc
  • 34,233
  • 10
  • 73
  • 98