Python的分解 [英] Python factorization

问题描述

我只是想知道，列出了一些所有的整数因素的最佳方法，因为它的主要因素及其指数的字典。
例如，如果我们有{2：3,3：2，5：1}（2 ^ 3 * 3 ^ 2 * 5 = 360）
然后，我可以写：

I'd just like to know the best way of listing all integer factors of a number, given a dictionary of its prime factors and their exponents.
For example if we have {2:3, 3:2, 5:1} (2^3 * 3^2 * 5 = 360)
Then I could write:

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

但在这里我有3可怕的循环。是否有可能摘要为特定的任何分解成一个字典对象参数？函数

But here I've got 3 horrible for loops. Is it possible to abstract this into a function given any factorization as a dictionary object argument?

推荐答案

嗯，不是只有你有3个循环，但如果你有超过3个因素这种做法是行不通的：）

Well, not only you have 3 loops, but this approach won't work if you have more than 3 factors :)

一种可能的方式：

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个因素，我们正在做的：

Also, you can avoid duplicating some work in the inner loop: if your working set is (1,3), and want to apply to 2^3 factors, we were doing:

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

看看我们有多少重复在第二组？

See how many duplicates we have in the second sets?

但我们可以做，而不是：

But we can do instead:

• （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）

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

该解决方案看起来即使没有套更好的：

The solution looks even nicer without the sets:

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

这篇关于Python的分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！