¿Cómo funciona la función de reducción?

Question

Por lo que yo entiendo, la función reducir toma una lista l y una función f. Luego, llama a la función f en los dos primeros elementos de la lista y luego llama repetidamente a la función f con el siguiente elemento de lista y el resultado anterior.

Por lo tanto, definen las siguientes funciones:

La siguiente función calcula el factorial.

def fact(n): 
    if n == 0 or n == 1: 
     return 1 
    return fact(n-1) * n 


def reduce_func(x,y): 
    return fact(x) * fact(y) 

lst = [1, 3, 1] 
print reduce(reduce_func, lst) 

Ahora, ¿no debería darme esto ((1! * 3!) * 1!) = 6? Pero, en su lugar, da 720. ¿Por qué 720? Parece tomar el factorial de 6 también. Pero, necesito entender por qué.

¿Alguien puede explicar por qué sucede esto y una solución temporal?

Básicamente quiero calcular el producto de factoriales de todas las entradas en la lista. El plan de copia de seguridad es ejecutar un ciclo y calcularlo. Pero, preferiría usar reducir.

Answer 1

Entendido:

necesito para trazar los números a sus factoriales primero y luego llamar a reducir con el operador se multiplican.

Por lo tanto, esto funcionaría:

lst_fact = map(fact, lst) 
reduce(operator.mul, lst_fact) 

Answer 2

Su función llama a fact() en ambos argumentos. Está calculando ((1! * 3!)! * 1!). La solución es sólo para llamar sólo en el segundo argumento, y pasar reduce() un valor inicial de 1.

Answer 3

Desde el Python reduce documentation,

reducir (función, secuencia) devuelve un solo valor calculado llamando a la (binario) funcionan en los primeros dos elementos de la secuencia, luego en el resultado y el siguiente elemento, y así sucesivamente.

Así que, caminando. Calcula reduce_func de los primeros dos elementos, reduce_func(1, 3) = 1! * 3! = 6. Luego, calcula reduce_func del resultado y el siguiente artículo: reduce_func(6, 1) = 6! * 1! = 720.

Olvidaste eso, cuando el resultado de la primera llamada reduce_func se pasa como entrada al segundo, se factoriza antes de la multiplicación.

Answer 4

Bueno, en primer lugar, su reduce_func no tiene la estructura de un pliegue; no coincide con su descripción de un pliegue (que es correcto).

La estructura de un pliegue es: def foldl(func, start, iter): return func(start, foldl(func, next(iter), iter)

Ahora, su función fact no opera en dos elementos - que sólo calcula factorial.

Por lo tanto, en resumen, no está utilizando un pliegue, y con esa definición de factorial, no es necesario.

Si desea jugar con factorial, echa un vistazo a la ordenada en el combinador: http://mvanier.livejournal.com/2897.html

Si usted quiere aprender acerca de pliegues, mira mi respuesta a esta pregunta, lo que demuestra su uso para calcular fracciones acumuladas : creating cumulative percentage from a dictionary of data

Answer 5

La forma más fácil de entender reducir() es mirar a su puro Python código equivalente:

def myreduce(func, iterable, start=None): 
    it = iter(iterable) 
    if start is None: 
     try: 
      start = next(it) 
     except StopIteration: 
      raise TypeError('reduce() of empty sequence with no initial value') 
    accum_value = start 
    for x in iterable: 
     accum_value = func(accum_value, x) 
    return accum_value 

Se puede ver que que sólo tiene sentido para su reduce_func() para aplicar el factorial al argumento más a la derecha:

def fact(n): 
    if n == 0 or n == 1: 
     return 1 
    return fact(n-1) * n 

def reduce_func(x,y): 
    return x * fact(y) 

lst = [1, 3, 1] 
print reduce(reduce_func, lst) 

Con esa pequeña revisión, el código produce como se esperaba :-)

Answer 6

También podría implementar factorial utilizando reducir.

def factorial(n): 
    return(reduce(lambda x,y:x*y,range(n+1)[1:])) 

Answer 7

Las otras respuestas son geniales. Voy a añadir simplemente un ejemplo ilustra que me parece bastante bueno para entender reduce():

>>> reduce(lambda x,y: x+y, [47,11,42,13]) 
113 

se calcularán de la siguiente manera:

(Source) (mirror)

Answer 8

Reducir ejecuta la función en el parámetro # 1 sucesivamente a través de los valores proporcionados por el iterador en el parámetro # 2

print '-------------- Example: Reduce(x + y) --------------' 

def add(x,y): return x+y 
x = 5 
y = 10 

import functools 
tot = functools.reduce(add, range(5, 10)) 
print 'reduce('+str(x)+','+str(y)+')=' ,tot 

def myreduce(a,b): 
    tot = 0 
    for i in range(a,b): 
     tot = tot+i 
     print i,tot 
    print 'myreduce('+str(a)+','+str(b)+')=' ,tot 

myreduce(x,y) 

print '-------------- Example: Reduce(x * y) --------------' 

def add(x,y): return x*y 
x = 5 
y = 10 

import functools 
tot = functools.reduce(add, range(5, 10)) 
print 'reduce('+str(x)+','+str(y)+')=' ,tot 

def myreduce(a,b): 
    tot = 1 
    for i in range(a,b): 
     tot = tot * i 
     print i,tot 
    print 'myreduce('+str(a)+','+str(b)+')=' ,tot 

myreduce(x,y)