Python Faktorisierung

Question

Ich möchte nur die beste Möglichkeit, alle Integer-Faktoren einer Zahl aufgelistet, mit einem Wörterbuch seiner Primfaktoren und deren Exponenten kennen.
Zum Beispiel, wenn wir {2: 3, 3: 2, 5: 1} (2^3 * 3^2 * 5 = 360)
Dann könnte ich schreiben:

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

Aber hier Ich habe 3 schreckliche Loops. Ist es möglich, dies bei einer Faktorisierung als Wörterbuchobjekt-Argument in eine Funktion zu abstrahieren?

Answer 1

Na ja, nicht nur Sie haben drei Schleifen, aber dieser Ansatz wird nicht funktionieren, wenn Sie mehr als 3 Faktoren :)

Eine Möglichkeit:

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 

auch können Sie vermeiden, einige Arbeiten in der inneren Schleife zu duplizieren: wenn Ihr Arbeitssatz (1,3) ist, und anwenden möchten 2^3 Faktoren, die wir taten:

• (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)

sehen, wie viele Duplikate wir in dem zweiten Satz haben?

Aber wir können stattdessen tun:

• (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)

Die Lösung ohne die Sätze noch schöner aussieht:

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

Grundsätzlich haben Sie hier einen Satz, der aus jedem Faktor der Zielnummer besteht. In Ihrem Beispiel wäre die Menge {2 2 2 3 3 5}. Jede strikte Teilmenge dieser Menge ist die Faktorisierung eines der Teiler Ihrer Zahl. Wenn Sie also alle Teilmengen dieser Menge erzeugen können, können Sie die Elemente jeder Teilmenge zusammen multiplizieren und alle Ganzzahl-Teiler erhalten.

Der Code sollte von dort ziemlich offensichtlich sein: eine Liste erzeugen, die die Faktorisierung enthält, alle Teilmengen dieser Liste erzeugen (Bonuspunkte für die Verwendung eines Generators; ich denke, es gibt eine relevante Funktion in der Standardbibliothek). Dann multipliziere und gehe von dort aus. Nicht optimal effizient, aber gut aussehend.

Answer 3

Mit itertools.product von 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) 

Beispiel:

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

Ausgang:

[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

Ja. Wenn Sie einen Algorithmus haben, dass n für Schleifen verschachtelt werden muss, können Sie in der Regel schalten Sie ihn in eine rekursive Funktion:

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

Ich habe blogged about this, und der schnellsten reine Python (ohne itertools) von Tim Peters auf die Python-Liste von einem Post kommt, und verwendet verschachtelte rekursive Generatoren:

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 

Beachten Sie, dass die Art und Weise geschrieben wird, ist es ein dauert Liste der Primfaktoren, kein Wörterbuch, dh [2, 2, 2, 3, 3, 5] anstelle von {2 : 3, 3 : 2, 5 : 1}.