Python分解

Question

我想知道列出一个数字的所有整数因子的最佳方法，给定了它的主要因子及其指数的字典。
例如，如果我们有{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个可怕的循环。给定任何因式分解作为字典对象参数，是否可以将其抽象为一个函数？

Answer 1

好吧，不仅您有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

此外，您还可以避免在内部循环中重复某些工作：如果您的工作集为（1,3），并且想应用到2 ^ 3个因子，那么我们正在做：

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

看看第二组中有多少个重复项？

但是我们可以改为：

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

没有设置，解决方案看起来更好：

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