Comportamiento extraño de las llamadas al filtro apilado()

Question

Así que estoy obteniendo un comportamiento interesante de algunos filtros apilados dentro de un ciclo for. Voy a empezar con una demostración:

>>> x = range(100) 
>>> x = filter(lambda n: n % 2 == 0, x) 
>>> x = filter(lambda n: n % 3 == 0, x) 
>>> list(x) 
[0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96] 

Aquí obtenemos el resultado esperado. Tenemos un rango dentro de un filtro dentro de un filtro, y las condiciones del filtro se están acumulando como queremos. Ahora aquí viene mi problema.
He escrito una función para calcular los números primos relativos de un número. Se ve así:

def relative_primes(num): 
    '''Returns a list of relative primes, relative to the given number.''' 
    if num == 1: 
     return [] 
    elif is_prime(num): 
     return list(range(1, num)) 
    result = range(1, num) 
    for factor in prime_factors(num): 
     # Why aren't these filters stacking properly?       
     result = filter(lambda n: n % factor != 0, result) 
    return list(result) 

Por alguna razón, sólo se está aplicando el filtro para el factor último de la lista adquirido de prime_factors(). Ejemplo:

>>> prime_factors(30) 
[2, 3, 5] 
>>> relative_primes(30) 
[1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29] 

Podemos ver que no se eliminaron múltiplos de 2 o 3 de la lista. ¿Por qué está pasando esto? ¿Por qué funciona el ejemplo anterior, pero los filtros en el bucle for no?

Answer 1

En Python 3.x, filter() devuelve un generador en lugar de una lista. Como tal, solo se utiliza el valor final de factor ya que los tres filtros usan el mismo factor. Tendrá que modificar su lambda ligeramente para que funcione.

result = filter(lambda n, factor=factor: n % factor != 0, result) 

Answer 2

La evaluación de los iteradores es floja. Todos los filtros serán evaluados solamente en la declaración

return list(result) 

En ese momento, el valor de factor es el último factor primordial. Las funciones lambda solo contienen una referencia al nombre local factor y usarán cualquier valor asignado a ese nombre en el momento de la ejecución.

Una forma de solucionar esto es convertir a una lista en cada iteración.

Como nota al margen, una aplicación mucho más fácil de esta función es

from fractions import gcd 
def relative_primes(n): 
    return [i for i in range(1, n) if gcd(n, i) == 1] 

Editar: Si usted está después de la actuación en lugar de simplicidad, también puedes probar esta:

def relative_primes(n): 
    sieve = [1] * n 
    for i in range(2, n): 
     if not sieve[i] or n % i: 
      continue 
     sieve[::i] = [0] * (n // i) 
    return list(itertools.compress(range(n), sieve)) 

Answer 3

Si te entendí correctamente y Dos enteros son relativamente primos si no comparten factores positivos comunes (divisores), excepto 1. Usando la notación para denotar el mayor divisor común, dos enteros a y b ar e relativamente primo si gcd (a, b) == 1. luego puede usar el módulo fractions de la siguiente manera.

from fractions import gcd 

num = 30 
relative_primes = filter(lambda x: gcd(x,num) == 1, xrange(1,num))