Python factorization

Question

Chciałbym po prostu wiedzieć, jak najlepiej wymienić wszystkie liczby całkowite liczby, biorąc pod uwagę słownik czynników i ich wykładników.
Na przykład jeśli mamy {2: 3, 3: 2, 5: 1} (2^3 * 3^2 * 5 = 360)
Wtedy mógłbym napisać:

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

ale tutaj Mam 3 okropne pętle. Czy można to przekształcić w funkcję, z uwzględnieniem jakiejkolwiek faktoryzacji jako argumentu obiektu słownikowego?

Answer 1

Dobrze, nie tylko masz 3 pętle, ale takie podejście nie będzie działać, jeśli masz więcej niż 3 czynniki :)

Jednym z możliwych sposobów:

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 

Ponadto, można uniknąć powielania niektórych prac w wewnętrznej pętli: jeśli zestaw roboczy jest (1,3), a chcą mieć zastosowanie do 2^3 czynniki, robiliśmy:

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

Zobacz, ile duplikatów mamy w drugich zbiorów?

Ale możemy zrobić zamiast:

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

Rozwiązanie wygląda jeszcze ładniej bez zestawów:

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

Zasadniczo masz tu zestaw, składający się z każdego czynnika liczby docelowej. W twoim przykładzie zestaw będzie miał postać {2 2 2 3 3 5}. Każdy ścisły podzbiór tego zestawu jest faktoryzacją jednego z dzielników twojego numeru, więc jeśli możesz wygenerować wszystkie podzbiory tego zbioru, możesz pomnożyć elementy każdego podzbioru i uzyskać wszystkie dzielniki całkowite.

Kod powinien być dość oczywisty: wygenerować listę zawierającą faktoryzację, wygenerować wszystkie podzbiory tej listy (punkty bonusowe za użycie generatora, myślę, że istnieje odpowiednia funkcja w standardowej bibliotece). Następnie pomnóż i odejdź stamtąd. Nie optymalnie efektywny w żaden sposób, ale ładnie wyglądający.

Answer 3

Stosując itertools.product Pythonie 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) 

przykład:

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

wyjściowa:

[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

Tak. Kiedy masz algorytmu, który potrzebuje n zagnieżdżone pętle, zazwyczaj można przekształcić go w funkcji rekurencyjnej:

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

mam blogged about this i najszybszy czysty python (bez itertools) pochodzi z postu Tim Peters do listy python i używa zagnieżdżonych rekurencyjne generatorów:

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 

Należy zauważyć, że sposób jest napisane, to bierze lista czynników głównych, a nie słownik, tj. [2, 2, 2, 3, 3, 5] zamiast {2 : 3, 3 : 2, 5 : 1}.