带有重复的非素因子分解

Question

假设我们有一些数字因子，比如1260：

>>> factors(1260)
[2, 2, 3, 3, 5, 7]

在Python中，如何找到这些数字的所有组合，得到每一种可能的乘积，也就是所有的因式分解，而不仅仅是质因数分解，并且这些因子的和要小于最大乘积呢？

如果我从质因数开始组合，我还得重新分解剩下的部分，因为我不知道哪些部分没有被组合在一起。

我也可以改进我的因子函数，让它生成因子的配对，而不是按大小顺序排列，但这样做对于最大乘积达到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个因子）。

更新2： 这是我的代码，但我必须弄清楚如何递归或迭代地进行多次移除，以处理长度大于2的部分，并深入挖掘词法分区，以替换产生重复的跳跃位模式（仅一个替换的命中计数很可怜，而且这还不包括在单一分区内的“单元素分区”的传递）：

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]]

与他在Python 2.7中运行的问题88的相关解决方案，根据我的计时装饰器，耗时4.85秒，经过优化停止条件后，找到的计数器在2.6.6中为3.4秒，使用psyco，在2.7中没有psyco为3.7秒。我自己的代码从接受答案中的代码（我移除了排序）耗时30秒，缩短到2.25秒（2.7没有psyco），在Python 2.6.6中使用psyco为782毫秒。

递归质因数组合数学动态规划因子分解筛选算法乘积约束重复因子

带有重复的非素因子分解

3 个回答

撰写回答