Yếu tố Python

Question

Tôi chỉ muốn biết cách tốt nhất để liệt kê tất cả các thừa số nguyên của một số, được cung cấp từ điển các yếu tố chính và số mũ của chúng.
Ví dụ, nếu chúng ta có {2: 3, 3: 2, 5: 1} (2^3 * 3^2 * 5 = 360)
Sau đó, tôi có thể viết:

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

Nhưng ở đây Tôi đã có 3 khủng khiếp cho các vòng lặp. Có thể trừu tượng điều này thành một hàm cho bất kỳ yếu tố nào như một đối số từ điển không?

Answer 1

Vâng, không chỉ bạn có 3 vòng, nhưng phương pháp này sẽ không hoạt động nếu bạn có hơn 3 yếu tố :)

Một cách có thể:

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 

Ngoài ra, bạn có thể tránh lặp lại một số công việc trong vòng lặp bên trong: nếu bộ làm việc của bạn là (1,3), và muốn áp dụng cho 2^3 yếu tố, chúng tôi đã thực hiện:

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

Xem có bao nhiêu bản sao chúng tôi có trong các bộ thứ hai?

Nhưng chúng ta có thể làm thay vì:

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

Các giải pháp trông thậm chí còn đẹp hơn nếu không có sự tập:

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

Về cơ bản, những gì bạn có ở đây là tập hợp, bao gồm từng yếu tố của số mục tiêu. Trong ví dụ của bạn, tập hợp sẽ là {2 2 2 3 3 5}. Mỗi tập hợp con nghiêm ngặt của tập hợp đó là hệ số của một trong số ước của số của bạn, vì vậy nếu bạn có thể tạo tất cả các tập hợp con của tập hợp đó, bạn có thể nhân các phần tử của từng tập con với nhau và nhận tất cả ước số nguyên.

Mã phải rõ ràng từ đó: tạo danh sách chứa yếu tố, tạo tất cả các tập hợp con của danh sách đó (điểm thưởng để sử dụng trình tạo; Tôi nghĩ có một hàm liên quan trong thư viện chuẩn). Sau đó nhân lên và đi từ đó. Không hiệu quả tối ưu bằng bất kỳ phương tiện nào, nhưng đẹp trai.

Answer 3

Sử dụng itertools.product từ 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) 

Ví dụ:

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

Output:

[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

Yes. Khi bạn đã có một thuật toán mà cần n lồng cho vòng, bạn thường có thể biến nó thành một hàm đệ quy:

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

Tôi có blogged about this, và trăn tinh khiết nhanh nhất (không có itertools) xuất phát từ một bài đăng bởi Tim Peters vào danh sách python, và sử dụng máy phát điện đệ quy lồng nhau:

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 

Lưu ý rằng cách thức mà nó được viết, phải mất một danh sách các yếu tố chính, không phải từ điển, tức là [2, 2, 2, 3, 3, 5] thay vì {2 : 3, 3 : 2, 5 : 1}.