我想知道在给定一个数字的质因数和它们的指数字典时,列出所有整数因数的最佳方法。
例如,如果我们有{2:3, 3:2, 5:1}(2^3 * 3^2 * 5 = 360),那么我可以这样写:
for i in range(4):
for j in range(3):
for k in range(1):
print 2**i * 3**j * 5**k
但是我这里有3个可怕的for循环。是否可以将其抽象成一个函数,并给定任何分解为字典对象参数的因子?
我想知道在给定一个数字的质因数和它们的指数字典时,列出所有整数因数的最佳方法。
例如,如果我们有{2:3, 3:2, 5:1}(2^3 * 3^2 * 5 = 360),那么我可以这样写:
for i in range(4):
for j in range(3):
for k in range(1):
print 2**i * 3**j * 5**k
但是我这里有3个可怕的for循环。是否可以将其抽象成一个函数,并给定任何分解为字典对象参数的因子?
我已经在博客中写过这个问题,最快的纯Python解决方案(不使用itertools)来自于Tim Peters在Python邮件列表上的一篇文章,使用了嵌套递归生成器:
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
请注意,代码中要求输入质因数的列表而非字典,即需要输入 [2, 2, 2, 3, 3, 5]
而非 {2 : 3, 3 : 2, 5 : 1}
。
使用Python 2.6中的itertools.product
:
#!/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)
示例:
print sorted(all_factors({2:3, 3:2, 5:1}))
输出:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60,
72, 90, 120, 180, 360]
product()
的纯Python实现。只有6行代码。 - jfs好的,不仅你有3个循环,而且如果你有超过3个因素,这种方法将无法工作 :)
一种可能的方法:
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
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
是的。当您有一个需要n个嵌套for循环的算法时,通常可以将其转换为递归函数:
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)
基本上,您在这里拥有的是一个集合,由目标数字的每个因子组成。在您的示例中,该集合将为{2 2 2 3 3 5}
。该集合的每个严格子集都是您数字的一个因数的分解,因此如果您可以生成该集合的所有子集,则可以将每个子集的元素相乘并获得所有整数因子。
从那里开始,代码应该很明显:生成一个包含因式分解的列表,生成该列表的所有子集(使用生成器获得奖励;我认为标准库中有一个相关函数)。然后进行乘法并继续进行。虽然不是最优效率,但看起来很好。