Come posso fare questa Python funzione ricorsiva restituire un elenco?

Occhiata a questa semplice funzione

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

Ecco il risultato di prime_factors(120)

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

Invece di nidificati tuple, voglio tornare un piatto tupla o di un elenco.

(2, 2, 2, 3, 5)

C’è un modo semplice per fare che?

 

5 Replies
  1. 20
    def prime_factors(n):
      for i in range(2,n):
        if n % i == 0:
          return [i] + prime_factors(n / i)
      return [n]
    • Invece di creare una nuova lista per ogni valore di ritorno, si potrebbe passare la lista come argomento e aggiungere ad essa. Se l’elenco diventa grande, questo può risparmiare un po ‘ di spazio e di tempo.
    • Un sacco di tempo …
    • Considerando l’algoritmo originale, non credo che le prestazioni, è fondamentale 🙂
    • In realtà, perché sarebbe risparmiare tempo e spazio?
    • aggiungere ad un elenco è più conveniente che la fusione delle liste in una copia. Per lunghi elenchi, la copia è costoso.
    • ah, non pensare che come aggiunta a una stringa attiva realloc di tutta la stringa ( come c#/java) 🙂

  2. 10
    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

    Esempio:

    >>> tuple(prime_factors(100))
    (2, 2, 5, 5)
  3. 7

    Senza modificare la funzione originale, da Python Trucchi:

    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
  4. 5

    liw.fi, come suggerito in una commento:

    Invece di creare una nuova lista per ogni valore di ritorno, si potrebbe passare l’elenco come un
    argomento e aggiungere ad essa. Se l’elenco diventa grande, questo può risparmiare un po ‘ di spazio e di tempo.

    Ecco un’implementazione di liw.fi suggerimento.

    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
    • Un aspetto negativo, però. Perché il bar=[] è solo inizializzato una volta, sarà sempre aggiungere elementi all’elenco stesso oggetto quando si chiama la funzione con un solo argomento (almeno in Python 2.x). Uso bar=Nessuno (…) se il bar è Nessuno: bar = []; invece.
    • Grazie! Ho corretto il codice.
  5. 1

    Non so come sia rilevante, ma questa funzione può aiutare appiattire profonda liste nidificate (usa la ricorsione), e può essere applicato per il problema a portata di mano. Anche se, è l’uso di un tubo per l’acqua di una margherita

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

Lascia un commento