how to use a generator in python to yield results from dfs?

Question

I have a dfs function (permutation) in which it takes long time to compute all possible values; I wish to create a generator such that every time I call a function get_value it will provide a possible outcome. So in the example below when calling get_value 3 times the results should be:

['1', '2', '3', '4']
['1', '2', '4', '3']

my current execution:

class Solution:
     
 def permutation(self, lst):
 
    if len(lst) == 0:
        return []
  
    if len(lst) == 1:
        return [lst]
  
    l = []
 
    for i in range(len(lst)):
       m = lst[i]
  
       remLst = lst[:i] + lst[i+1:]
       for p in self.permutation(remLst):
           l.append([m] + p)
    return l

 #def get_value():
 #      yield ???

if __name__=='__main__':
    
    s = Solution()
    r = s.permutation(['1','2','3','4']) 

    for p in r:
        print (p)

    #what I want is:
    s = Solution()
    v1 = s.get_value() #['1', '2', '3', '4']
    v2 = s.get_value() #['1', '2', '4', '3']
    #and so forth

Does this answer your question? [What does the "yield" keyword do?](https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do) — Dominik Stańczak, Aug 12 '22 at 14:32
@DominikStańczak0 no. I wish to know how to implement it on a recursive function. — pylos, Aug 12 '22 at 14:34
Related [Why does "yield" work in a recursive function](https://stackoverflow.com/questions/71966242/why-does-yield-work-in-a-recursive-function) — rochard4u, Aug 12 '22 at 14:54

score 1 · Answer 1 · answered Aug 12 '22 at 14:44

1

There is a built-in for this: permutations from the package itertools (no pip install required):

from itertools import permutations
r = permutations(['1','2','3','4'])

next(r)
# ('1', '2', '3', '4')
next(r)
# ('1', '2', '4', '3')
next(r)
# ('1', '3', '2', '4')
next(r)
# ('1', '3', '4', '2')

...

answered Aug 12 '22 at 14:44

Joe Carboni

421
1
6

@JoeCabonbi this doesnt answer my question at all. I wish to know how to implement the next on my dfs. – pylos Aug 12 '22 at 14:48

score 0 · Accepted Answer · answered Aug 12 '22 at 14:50

For yields in recursion, you can use yield from

    def permutation(self, lst):

        if len(lst) == 0:
            return

        if len(lst) == 1:
            yield lst

        for i in range(len(lst)):
            m = lst[i]

            remLst = lst[:i] + lst[i+1:]
            yield from ([m] + p for p in self.permutation(remLst))

The for loop will still work:

r = s.permutation(['1', '2', '3', '4'])
for p in r:
    print(p)

Instead of get_value, you should use next():

r = s.permutation(['1', '2', '3', '4'])
print(next(r))
print(next(r))
print(next(r))

Just be aware that the for loop consumes the iterator:

r = s.permutation(['1', '2', '3', '4'])
for p in r:
    print(p)
r = s.permutation(['1', '2', '3', '4']) # Reset the iterator otherwise `next` will fail
print(next(r))
print(next(r))
print(next(r))

score 0 · Answer 3 · answered Aug 12 '22 at 14:52

Use yield from:

def permutation(self, lst):
    if not lst:
        return []
    if len(lst) == 1:
        yield lst
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i+1:]
        yield from ([m] + p for p in self.permutation(remLst))

Then, use next:

it = s.permutation(['1', '2', '3', '4'])
print(next(it)) # ['1', '2', '3', '4']
print(next(it)) # ['1', '2', '4', '3']
print(next(it)) # ['1', '3', '2', '4']

how to use a generator in python to yield results from dfs?

3 Answers3