Necesito reescribir este horrible fragmento de código usando la recursividad en Python. La profundidad de la anidación debería depender del argumento de la función rec pero, en general, me gustaría que fuera la longitud de la variable "a", que es una cadena. Le agradecería cualquier respuesta y pistas sobre cómo abordar este problema.

def rec():
    count=0
    for i in range(len(letters)):
        for j in range(i+1, len(letters)):
            if letters[i]+letters[j] in a:
                for k in range(j+1, len(letters)):
                    if letters[i]+letters[j]+letters[k] in a:
                        if letters[i]+letters[j]+letters[k]==a:
                            count+=1
                        else:
                            for l in range(k+1, len(letters)):
                                if letters[i]+letters[j]+letters[k]+letters[l]==a:
                                    count+=1

    return count
-1
morteify 4 mar. 2018 a las 23:43

3 respuestas

La mejor respuesta

FWIW, algunos tipos de lógica combinatoria se expresan más fácilmente con itertools que con recursividad Por ejemplo, cuando ocurre este patrón:

letters = 'ABCDEF'
for i in range(len(letters)):
    a = letters[i]
    for j in range(i+1, len(letters)):
        b = letters[j]
        for k in range(j+1, len(letters)):
            c = letters[k]
            print(a, b, c)

Se puede reemplazar con esto:

from itertools import combinations

letters = 'ABCDEF'
for a, b, c in combinations(letters, 3):
    print(a, b, c)

Hay más en su pregunta que esto, pero quería señalar que las funciones combinatorias son un buen punto de partida para el tipo de lógica planteada en esta pregunta.

5
Raymond Hettinger 4 mar. 2018 a las 21:06

Este horrible código puede reescribirse como se muestra a continuación en forma iterativa, pero reducirá la eficiencia. Lo mismo se aplica a la función recursiva.

def rec():
    count=0
    for i in range(len(letters)):
        for j in range(i+1, len(letters)):
            for k in range(j+1, len(letters)):
                if letters[i]+letters[j]+letters[k]==a:
                     count+=1
                     continue
                for l in range(k+1, len(letters)):
                    if letters[i]+letters[j]+letters[k]+letters[l]==a:
                         count+=1

    return count
0
sonus21 4 mar. 2018 a las 20:51

Solo una solución recursiva ...

def rec(letters, a):
    return sum(rec(letters[i+1:], a[1:])
               for i, c in enumerate(letters)
               if c == a[0]) if a else 1

Demo:

>>> rec('onerene', 'one')
4
0
Stefan Pochmann 4 mar. 2018 a las 23:13