Рекурсивный генератор перестановок python

Can generators be recursive?

All I got was the first item 6 . Is there a way to make such code work? Essentially transferring the yield command to the level above in a recursion scheme?

You’re not yielding when you call it again. It hits the first yield, doesn’t see another yield statement, and exits.

you either need to yield from another_generator() , or yield each element one by one explicitly in while loop. Whether another_generator() is or is not «recursive» in your terminology — that does not matter.

7 Answers 7

def recursive_generator(lis): yield lis[0] yield from recursive_generator(lis[1:]) for k in recursive_generator([6,3,9,1]): print(k) 

I should point out this doesn’t work because of a bug in your function. It should probably include a check that lis isn’t empty, as shown below:

def recursive_generator(lis): if lis: yield lis[0] yield from recursive_generator(lis[1:]) 

In case you are on Python 2.7 and don’t have yield from , check this question out.

To simplify that verbose python.org doc explaining yield from , yield from g is essentially equivalent to for x in g: yield x

Why your code didn’t do the job

In your code, the generator function:

1. returns (yields) the first value of the list
2. then it creates a new iterator object calling the same generator function, passing a slice of the list to it
3. and then stops

The second instance of the iterator, the one recursively created, is never being iterated over. That’s why you only got the first item of the list.

A generator function is useful to automatically create an iterator object (an object that implements the iterator protocol), but then you need to iterate over it: either manually calling the next() method on the object or by means of a loop statement that will automatically use the iterator protocol.

So, can we recursively call a generator?

The answer is yes. Now back to your code, if you really want to do this with a generator function, I guess you could try:

def recursive_generator(some_list): """ Return some_list items, one at a time, recursively iterating over a slice of it. """ if len(some_list)>1: # some_list has more than one item, so iterate over it for i in recursive_generator(some_list[1:]): # recursively call this generator function to iterate over a slice of some_list. # return one item from the list. yield i else: # the iterator returned StopIteration, so the for loop is done. # to finish, return the only value not included in the slice we just iterated on. yield some_list[0] else: # some_list has only one item, no need to iterate on it. # just return the item. yield some_list[0] some_list = [6,3,9,1] for k in recursive_generator(some_list): print(k) 

Note: the items are returned in reversed order, so you might want to use some_list.reverse() before calling the generator the first time.

The important thing to note in this example is: the generator function recursively calls itself in a for loop, which sees an iterator and automatically uses the iteration protocol on it, so it actually gets values from it.

This works, but I think this is really not useful. We are using a generator function to iterate over a list and just get the items out, one at a time, but. a list is an iterable itself, so no need for generators! Of course I get it, this is just an example, maybe there are useful applications of this idea.

Another example

Let’s recycle the previous example (for lazyness). Lets say we need to print the items in a list, adding to every item the count of previous items (just a random example, not necessarily useful).

def recursive_generator(some_list): """ Return some_list items, one at a time, recursively iterating over a slice of it. and adding to every item the count of previous items in the list """ if len(some_list)>1: # some_list has more than one item, so iterate over it for i in recursive_generator(some_list[1:]): # recursively call this generator function to iterate over a slice of some_list. # return one item from the list, but add 1 first. # Every recursive iteration will add 1, so we basically add the count of iterations. yield i + 1 else: # the iterator returned StopIteration, so the for loop is done. # to finish, return the only value not included in the slice we just iterated on. yield some_list[0] else: # some_list has only one item, no need to iterate on it. # just return the item. yield some_list[0] some_list = [6,3,9,1] for k in recursive_generator(some_list): print(k) 

Now, as you can see, the generator function is actually doing something before returning list items AND the use of recursion starts to make sense. Still, just a stupid example, but you get the idea.

Note: off course, in this stupid example the list is expected to contain only numbers. If you really want to go try and break it, just put in a string in some_list and have fun. Again, this is only an example, not production code!

Источник

Recursive Permutation Generator, swapping list items not working

I want to systematically generate permutations of the alphabet. I cannot don’t want to use python itertools.permutation, because pregenerating a list of every permutation causes my computer to crash (first time i actually got it to force a shutdown, it was pretty great). Therefore, my new approach is to generate and test each key on the fly. Currently, I am trying to handle this with recursion. My idea is to start with the largest list (i’ll use a 3 element list as an example), recurse in to smaller list until the list is two elements long. Then, it will print the list, swap the last two, print the list again, and return up one level and repeat. For example, for 123

 23 --> 123 (swap position 1 with position 1) 32 --> 132 (swap position 1 with position 2) 

 13 --> 213 (swap position 1 with position 1) 31 --> 231 (swap position 1 with position 2) 

 21 --> 321 (swap position 1 with position 1) 12 --> 312 (swap position 1 with position 2) 

 234 (swap position 1 with position 1) 34 --> 1234 43 --> 1243 324 (swap position 1 with position 2) 24 --> 1324 42 --> 1342 432 (swap position 1 with position 3) 32 --> 1432 23 --> 1423 

2134 (swap position 0 for position 1) 134 (swap position 1 with position 1) 34 —> 2134 43 —> 2143 314 (swap position 1 with position 2) 14—> 2314 41—> 2341 431 (swap position 1 with position 3) 31—> 2431 13 —>2413

This is the code i currently have for the recursion, but its causing me a lot of grief, recursion not being my strong suit. Here’s what i have.

def perm(x, y, key): print "Perm called: X=",x,", Y=",y,", key=",key while (x 
python
recursion
generator
permutation