CODEWITHSUNDEEP
pythonrecursionpython-itertoolscombinatoricsyield
JRL
JRL

Reputation: 3

Getting results for a generator inside recursive function

Im trying to replicate the function from itertools.permutations() for purely didactic reasons.

One way of doing it was using lists of 1s, where 0 marks that a given elements has already being used.

So for instance, a list of letters:

list_l = ['a','b','c']

and the list [0,1,1] marks that a has already being used.

I pass this list to same function, and it generates the sublists [0,0,1] and [0,1,0] which corresponds to letters b being selected and c by elimination for the first list and c and then b for the second.

This method of marking the letters in positions of a list, requires me to keep an historial for each position of the combination, so even though I get the correct result I would like to make the function a generator giving one result at a time, but I don't know how to do it without breaking the recursivity and therefore destroying the program. I need the return for keeping the historial clean for the next element to be generated and i doubt it is possible to use yield and return in parallel.

I leave my code here. Thank you

def generate_string(list, a):
    comb = ''
    for n, v in enumerate(a[0]):
        if v==0:
            comb = comb + lista[n]
    for i in range(len(a)-1):
        for n,j in enumerate(zip(a[i], a[i+1])):
            if j[0] != j[1]:
                comb = comb + lista[n]
    for n, v in enumerate(a[-1]):
        if v==1:
            comb = comb + lista[n]
            
    return comb

def comb(lista, uns = None, historial = []):
    if uns == None:
        l = [1] *len(lista)
        comb(lista, uns = l)
        
    else:
        if sum(uns) == 1:
            print(generate_string(lista, historial).upper())
            return historial[:-1]
        else:
            for n, valor in enumerate(uns):
                uns2 = copy.deepcopy(uns)
                if valor == 1:
                    uns2[n] = 0
                    historial.append(uns2)
                    historial = comb(lista, uns2, historial) 
                    
            return historial[:-1]

lista = ['a','b','c','d']
comb(lista)

Upvotes: 0

Views: 108

Answers (1)

Tim Roberts
Tim Roberts

Reputation: 54698

Here is the recursive way to do permutations. The theory here is that, for each element in the list, you generate that element PLUS the permutations of the other elements in the list. Eventually, you get down to a spot where there are no more options to permute, and at that point you have a complete permutation to return. "yield from" is a passthrough, just passing the complete permutations yielded from the deeper calls.

lst = ['a','b','c','d']

def perm(lst, pfx=[]):
    if not lst:
        yield pfx
    for i in range(len(lst)):
        yield from perm( lst[0:i]+lst[i+1:], pfx+[lst[i]] )

print( list(perm(lst)))

Upvotes: 1

Related Questions