python - resueltos - reglas de recursividad

¿Cómo puedo hacer que esta función recursiva de Python devuelva una lista plana?

Question

Mira esta simple función

def prime_factors(n):
for i in range(2,n):
if n % i == 0:
return i, prime_factors(n / i)
return n

Aquí está el resultado de prime_factors(120)

(2, (2, (2, (3, 5))))

En lugar de tuplas anidadas, quiero que devuelva una sola tupla o lista plana.

(2, 2, 2, 3, 5)

¿Hay una manera simple de hacer eso?

Answer 1

Sin cambiar la función original, de los Trucos de Python :

def flatten(x):
"""flatten(sequence) -> list
Returns a single, flat list which contains all elements retrieved
from the sequence and all recursively contained sub-sequences
(iterables).
Examples:
>>> [1, 2, [3,4], (5,6)]
[1, 2, [3, 4], (5, 6)]
>>> flatten([[[1,2,3], (42,None)], [4,5], [6], 7, MyVector(8,9,10)])
[1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]"""
result = []
for el in x:
#if isinstance(el, (list, tuple)):
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result

Answer 2

def prime_factors(n):
for i in range(2,n):
if n % i == 0:
yield i
for p in prime_factors(n / i):
yield p
return
yield n

Ejemplo:

>>> tuple(prime_factors(100))
(2, 2, 5, 5)

Answer 3

def prime_factors(n):
for i in range(2,n):
if n % i == 0:
return [i] + prime_factors(n / i)
return [n]

Answer 4

liw.fi sugirió en un comentario :

En lugar de crear una nueva lista para cada valor devuelto, puede pasar la lista como argumento y anexarla. Si la lista es grande, esto puede ahorrar espacio y tiempo.

Aquí hay una implementación de la sugerencia de liw.fi.

def prime_factors(n, factors=None):
if factors is None:
factors = []
for i in range(2,n):
if n % i == 0:
factors.append(i)
return prime_factors(n / i, factors)
factors.append(n)
return factors

Answer 5

No sé qué tan relevante es esto, pero esta función puede ayudarlo a aplanar listas anidadas profundas ( usa recursividad ), y también puede aplicarse al problema en cuestión. Sin embargo, está usando una manguera para regar una margarita

def flatten(S):
if S == []:
return S
if isinstance(S[0], list):
return flatten(S[0]) + flatten(S[1:])
return S[:1] + flatten(S[1:])