Factorización Python

Question

Me gustaría saber la mejor manera de enumerar todos los factores enteros de un número, dado un diccionario de sus factores primos y sus exponentes.
Por ejemplo si tenemos {2: 3, 3: 2, 5: 1} (2^3 * 3^2 * 5 = 360)
Entonces podría escribir:

for i in range(4): 
    for j in range(3): 
    for k in range(1): 
     print 2**i * 3**j * 5**k 

Pero aquí Tengo 3 horribles bucles. ¿Es posible abstraer esto en una función dada cualquier factorización como un argumento de objeto de diccionario?

Answer 1

Bueno, no sólo tiene 3 bucles, pero este método no funcionará si tiene más de 3 factores :)

Una forma posible:

def genfactors(fdict):  
    factors = set([1]) 

    for factor, count in fdict.iteritems(): 
     for ignore in range(count): 
      factors.update([n*factor for n in factors]) 
      # that line could also be: 
      # factors.update(map(lambda e: e*factor, factors)) 

    return factors 

factors = {2:3, 3:2, 5:1} 

for factor in genfactors(factors): 
    print factor 

Además, se puede evitar la duplicación de algunos trabajos en el bucle interno: si su conjunto de trabajo es (1,3), y desea aplicar a 2^3 factores, estábamos haciendo:

• (1,3) U (1,3)*2 = (1,2,3,6)
• (1,2,3,6) U (1,2,3,6)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) U (1,2,3,4,6,12)*2 = (1,2,3,4,6,8,12,24)

Ver el número de duplicados que tenemos en los segundos juegos?

Pero podemos hacer en su lugar:

• (1,3) + (1,3)*2 = (1,2,3,6)
• (1,2,3,6) + ((1,3)*2)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) + (((1,3)*2)*2)*2 = (1,2,3,4,6,8,12,24)

La solución se ve aún más agradable sin los conjuntos:

def genfactors(fdict): 
    factors = [1] 

    for factor, count in fdict.iteritems(): 
     newfactors = factors 
     for ignore in range(count): 
      newfactors = map(lambda e: e*factor, newfactors) 
      factors += newfactors 

    return factors 

Answer 2

Básicamente, lo que tiene aquí es un conjunto, que consta de cada factor del número de destino. En su ejemplo, el conjunto sería {2 2 2 3 3 5}. Cada subconjunto estricto de ese conjunto es la factorización de uno de los divisores de tu número, por lo que si puedes generar todos los subconjuntos de ese conjunto, puedes multiplicar los elementos de cada subconjunto y obtener todos los divisores enteros.

El código debería ser bastante obvio a partir de allí: generar una lista que contenga la factorización, generar todos los subconjuntos de esa lista (puntos de bonificación por usar un generador; creo que hay una función relevante en la biblioteca estándar). Luego, multiplique y vaya desde allí. No es óptimamente eficiente de ninguna manera, pero agradable.

Answer 3

Usando itertools.product de Python 2.6:

#!/usr/bin/env python 
import itertools, operator 

def all_factors(prime_dict): 
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()] 
    for multipliers in itertools.product(*series): 
     yield reduce(operator.mul, multipliers) 

Ejemplo:

print sorted(all_factors({2:3, 3:2, 5:1})) 

de salida:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 
72, 90, 120, 180, 360] 

Answer 4

Sí. Cuando se tiene un algoritmo que necesita n bucles for anidados, por lo general puede convertirlo en una función recursiva:

def print_factors(d, product=1): 
    if len(d) == 0:  # Base case: we've dealt with all prime factors, so 
     print product # Just print the product 
     return 
    d2 = dict(d)   # Copy the dict because we don't want to modify it 
    k,v = d2.popitem() # Pick any k**v pair from it 
    for i in range(v+1): # For all possible powers i of k from 0 to v (inclusive) 
         # Multiply the product by k**i and recurse. 
     print_factors(d2, product*k**i) 

d = {2:3, 3:2, 5:1} 
print_factors(d) 

Answer 5

tengo blogged about this, y la pitón más rápido puro (sin itertools) proviene de un mensaje por Tim Peters a la lista de pitón, y utiliza generadores recursivas anidados:

def divisors(factors) : 
    """ 
    Generates all divisors, unordered, from the prime factorization. 
    """ 
    ps = sorted(set(factors)) 
    omega = len(ps) 

    def rec_gen(n = 0) : 
     if n == omega : 
      yield 1 
     else : 
      pows = [1] 
      for j in xrange(factors.count(ps[n])) : 
       pows += [pows[-1] * ps[n]] 
      for q in rec_gen(n + 1) : 
       for p in pows : 
        yield p * q 

    for p in rec_gen() : 
     yield p 

Tenga en cuenta que la forma en que está escrito, se necesita una lista de factores primos, no un diccionario, es decir, [2, 2, 2, 3, 3, 5] en lugar de {2 : 3, 3 : 2, 5 : 1}.