假设我们有数字因子，例如1260：
>>> factors(1260)
[2, 2, 3, 3, 5, 7]
在Python组合中，从这些数字中获得每个可能的子产品的最佳方法是哪种，即所有因子，不仅是素因子，而且因子之和小于max_product？
如果我根据主要因素进行组合，则我必须重构产品的其余部分，因为我不知道其余部分是否不能组合。
我还可以改进除数功能，以生成成对的除数，而不是按尺寸顺序生成除数，但是对于产品最大为12000的数量，仍然要花费我这样做。产品必须始终保持不变。
我与除数例程联系在一起，但是值得证明他们采用我的其他代码看起来并不值得。至少我的除数函数明显比sympy之一快：
def divides(number):
if number<2:
yield number
return
high = [number]
sqr = int(number ** 0.5)
limit = sqr+(sqr*sqr != number)
yield 1
for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit):
if not number % divisor:
yield divisor
high.append(number//divisor)
if sqr*sqr== number: yield sqr
for divisor in reversed(high):
yield divisor
重用此代码的唯一问题是将除数链接到因数筛子上或对除数的除数成对进行某种处理，我将其成对给出，而不是按顺序排序。
结果示例如下：
[4, 3, 3, 5, 7] (one replacement of two)
[5, 7, 36] (one replacement of three)
[3, 6, 14, 5] (two replacements)
可能我需要一些方法来为较小的除数生成筛分或动态编程解决方案，这些解决方案可以与除数为数字的数字相关联。看起来很难避免重叠。我确实准备好了一个筛子功能，该功能可以为每个数字存储最大的质因数，以加快分解速度，而无需保存每个数字的完整分解因数...也许可以进行调整。
更新：因素的总和应接近乘积，因此答案中可能存在数量众多的
UPDATE2：
这是我的代码，但必须弄清楚如何对长度大于2的部分进行递归或迭代多次删除，并挖掘词法分区以替换产生重复项的跳跃位模式（可悲的命中次数仅一次替换，而不会这样）计算“单元素分割”在single_partition内部的通过）：
from __future__ import print_function
import itertools
import operator
from euler import factors
def subset(seq, mask):
""" binary mask of len(seq) bits, return generator for the sequence """
# this is not lexical order, replace with lexical order masked passing duplicates
return (c for ind,c in enumerate(seq) if mask & (1<<ind))
def single_partition(seq, n = 0, func = lambda x: x):
''' map given function to one partition '''
for n in range(n, (2**len(seq))):
result = tuple(subset(seq,n))
others = tuple(subset(seq,~n))
if len(result) < 2 or len(others) == 0:
#empty subset or only one or all
continue
result = (func(result),)+others
yield result
if __name__=='__main__':
seen, hits, count = set(), 0, 0
for f in single_partition(factors(13824), func = lambda x: reduce(operator.mul, x)):
if f not in seen:
print(f,end=' ')
seen.add(f)
else:
hits += 1
count += 1
print('\nGenerated %i, hits %i' %(count,hits))
补充我很高兴在非质数部分中仅获得最多5个因数的因式分解。我亲手发现，最多减少5个相同因素的不减价安排采用以下形式：
partitions of 5 applied to 2**5
1 1 1 1 1 2 2 2 2 2
1 1 1 2 2 2 2 4
1 1 1 3 2 2 8
1 2 2 2 4 4
1 4 2 16
2 3 4 8
解决方案
我没有从良好的解决方案中删除可接受的答案，但这对工作来说太复杂了。从欧拉计画中，我仅揭示了来自新西兰Orbifold的此辅助功能，它的运行速度更快，并且不需要首先考虑主要因素：
def factorings(n,k=2):
result = []
while k*k <= n:
if n%k == 0:
result.extend([[k]+f for f in factorings(n/k,k)])
k += 1
return result + [[n]]
由我的定时装饰器在4.85 s中于Python 2.7中运行他的问题88的相关解决方案，并在通过使用psyco在2.6.6中发现计数器3.4 s，在未使用psyco的2.7中发现3.7 s优化了停止条件之后。我自己的代码速度从接受答案的代码（删除我添加的排序）后的30秒提高到2.25 s（不使用psyco时为2.7）和python 2.6.6中使用psyco时为782 ms。
最佳答案
我使用像[(2, 9), (3, 3)]（对于[2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]）的列表作为未扩展因子的基本列表和扩展因子的列表。在每个回合中，我从基础中选择一个因素，以减少其数量，然后
将其添加到扩展列表中，增加其长度，因此我们总共有一个附加因素（直到cufoff为止）
将其与所有扩展因子相乘，产生所有可能性
通过动态编程和截止策略，这变得非常快：
from itertools import groupby
def multiplicies( factors ):
""" [x,x,x,,y,y] -> [(x,3), (y,2)] """
return ((k, sum(1 for _ in group)) for k, group in groupby(factors))
def combinate(facs, cutoff=None):
facs = tuple(multiplicies(facs))
results = set()
def explode(base, expanded):
# `k` is the key for the caching
# if the function got called like this before return instantly
k = (base, expanded)
if k in results:
return
results.add(k)
# pick a factor
for (f,m) in base:
# remove it from the bases
newb = ((g, (n if g!=f else n-1)) for g,n in base)
newb = tuple((g,x) for g,x in newb if x > 0)
# do we cutoff yet?
if cutoff is None or len(newb) + len(expanded) < cutoff:
explode(newb, tuple(sorted(expanded + (f,))))
# multiply the pick with each factor in expanded
for pos in range(len(expanded)):
newexp = list(expanded)
newexp[pos] *= f
explode(newb, tuple(sorted(newexp)))
explode(facs, ())
# turn the `k` (see above) into real factor lists
return set((tuple((x**y) for x,y in bases) + expanded)
for (bases, expanded) in results)
# you dont even need the cutoff here!
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3])
# but you need it for
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3,5,7,9,11], 5)
如果可以，请尝试Psyco（我不能，因为我这里只有Py2.7），它也可能会大大加快速度。