假设我们有数字因子，例如 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
重用此代码的唯一问题是将除数链接到分解筛或对除数的除数执行某种 itertools.product，我将成对给出，而不是按顺序排序。
示例结果为：
[4, 3, 3, 5, 7] (one replacement of two)
[5, 7, 36] (one replacement of three)
[3, 6, 14, 5] (two replacements)
可能我需要一些方法来为较小的除数生成筛子或动态编程解决方案，这些除数可能与它们的除数相关联。看起来很难避免重叠。我确实准备了一个筛子函数，它为每个数字存储最大的素数，以加快分解速度，而不保存每个数字的完整分解……也许可以调整。
更新：因子的总和应该接近产品，因此答案中可能有大量 <= 10 的因子（最多 14 个因子）。
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
解决方案 我不会从好的解决方案中删除已接受的答案，但它对于这项工作来说过于复杂。从 Project Euler 我只揭示了来自 NZ 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 秒内运行 Python 2.7 的问题 88的相关解决方案，并在使用 psyco 的 2.6.6 中找到计数器 3.4 秒优化停止条件后，在没有 psyco 的 2.7 中找到 3.7 秒。在 Python 2.6.6 中，我自己的代码速度从 30 秒（使用接受答案的代码（由我添加的排序删除））到 2.25 秒（2.7 没有 psyco）和782 毫秒（使用 psyco）。