java - 查找整数的所有分解的算法

是否有一种算法可以找到整数的所有分解，最好在Python/Java中找到，但是欢迎任何反馈。

我有一种算法可以计算主要因子。例如[2,2,5]是20的主要因素。

def prime_factorization(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n /= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

我也有一种算法可以计算算法的所有因子(素数和非素数)。例如，20的因子是[1, 2, 4, 5, 10, 20]。

def factors(n):
    a, r = 1, [1]
    while a * a < n:
        a += 1
        if n % a: continue
        b, f = 1, []
        while n % a == 0:
            n //= a
            b *= a
            f += [i * b for i in r]
        r += f
    if n > 1: r += [i * n for i in r]
    return sorted(r)

我正在寻找的是一种算法，用于返回给定整数的所有因式分解(而不是因式)。对于整数20，该算法将产生以下结果:

[1,20]
[2,10]
[4,5]
[2,2,5]

谢谢!

最佳答案

这是一种效率很低的方法。它会生成大量重复项，然后在将它们返回之前将其过滤掉。

这个想法是您从n=1到len(factors)包含因子进行乘积，然后递归到未使用的因子。

import itertools


def mult(fs):
    res = 1
    for f in fs:
        res *= f
    return res


def _generate_all_factorizations(factors):
    if len(factors) <= 1:
        yield factors
        return

    for factors_in_mult in xrange(1, len(factors)+1):
        for which_is in itertools.combinations(range(len(factors)), factors_in_mult):
            this_mult = mult(factors[i] for i in which_is)
            rest = [factors[i] for i in xrange(len(factors)) if i not in which_is]

            for remaining in _generate_all_factorizations(rest):
                yield [this_mult] + remaining

我添加了一个函数来删除重复项并返回排序良好的函数:

def generate_all_factorizations(factors):
    seen = set()
    res = []
    for f in _generate_all_factorizations(factors):
        f = tuple(sorted(f))
        if f in seen:
            continue
        seen.add(f)
        yield f

现在，只需输入您的主要分解因子即可:

for factorization in generate_all_factorizations([2, 2, 5]):
    print factorization
print "----"
for factorization in generate_all_factorizations([2, 3, 5, 7]):
    print factorization

结果:

(2, 2, 5)
(2, 10)
(4, 5)
(20,)
----
(2, 3, 5, 7)
(2, 3, 35)
(2, 5, 21)
(2, 7, 15)
(2, 105)
(3, 5, 14)
(3, 7, 10)
(3, 70)
(5, 6, 7)
(5, 42)
(7, 30)
(6, 35)
(10, 21)
(14, 15)
(210,)