Getting results for a generator inside recursive function

Question

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)

Note: `historial=[]` this is bad. See why here: https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument — Woodford, May 04 '21 at 18:23
The recursion depth is equal to the length of the list. It will not exceed the stack capacity for any list that will complete in human time. Recursion is a fine way to solve this. — Tim Roberts, May 04 '21 at 18:31
What would you suggest? to my understanding, at any given point we the stack would only have at most n levels deep of recursion, being n the amount of elements to permutate. And historial would have at any point at most n-1 elements, and the loops n-1 elements to keep track of — JRL, May 04 '21 at 18:33

Tim Roberts · Accepted Answer · 2021-05-04T18:43:30.267

1

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)))

edited May 04 '21 at 18:43

answered May 04 '21 at 18:32

Tim Roberts

48,973
4
21
30

Got some homework to do to understand this, really appreciate the answer!! ps: what is gen? it's given me an error – JRL May 04 '21 at 18:37
Ack, that was the original name of the function. I will fix. – Tim Roberts May 04 '21 at 18:43

Getting results for a generator inside recursive function

1 Answers1