python - 如何生成一个数字的所有可能的除数积？

Question

我正在努力实现一种算法，该算法可以为我提供一些可能的产品。例如，对于 N=24这些是:

24*1, 12*2, 8*3, 6*4, 4*3*2, 3*2*2*2

我实现了一个函数，可以计算给定数字的质因数及其幂(例如 2^3 和 3^1 对于 N=24 )。但我不知道如何从质因数中得到除数组合。

编辑:这是我尝试过的:

def divisors(factors): # prime factors, e.g. [2,2,2,3] for 24
    yield list(factors)

    d = factors.pop()

    for i in range(len(factors)):
        m = [d*factors[i]] + factors[:i] + factors[i+1:]
        yield from divisors(m)

Answer 1

您没有说明您需要它来工作的大小数字，或者速度是否是一个问题，但这是一个非常简单的未优化的解决方案，对于小输入( n 小于 10**7 ，应该可以很好地工作，说)。

def products(n, min_divisor=2):
    """Generate expressions of n as a product of ints >= min_divisor."""
    if n == 1:
        yield []
    for divisor in range(min_divisor, n+1):
        if n % divisor == 0:
            for product in products(n // divisor, divisor):
                yield product + [divisor]

为了解释代码，请考虑如何手动有条不紊地完成此操作。您可以从包含 2 的产品开始。如果n很奇怪，没有。如果n是偶数，那么我们可以做一个简单的递归:找到n // 2的所有可能的分解，然后输出decomposition * 2为每一个。一旦我们用尽了所有包含 2 的产品，我们继续讨论涉及 3 的产品。但这里还有一个额外的复杂性:在第一步中，我们已经找到了涉及 2 的所有产品。 ，因此为了避免重复的解决方案，我们希望限制每个除数至少为 3 的乘积。 。因此，我们的递归调用需要跟踪允许的最小除数 min_divisor多于。最后，我们需要一个基本案例:1可表示为空乘积。

这是 n=24 的输出，包括 6*2*2您错过的案例:

>>> for product in products(24):
...     print('*'.join(map(str, product)))
... 
3*2*2*2
6*2*2
4*3*2
12*2
8*3
6*4
24

但这并不令人满意:正如其他评论者指出的那样，应该可以计算 n 的乘法分区从素数分解，甚至只是从素数分解中的指数列表，仅在需要重建因子时才使用素数。这是上述的一个变体，适用于现有的质因数分解。效率仍有很大的提升空间:特别是 itertools.product调用和后续过滤以忽略按字典顺序小于 min_exponents 的所有内容应替换为从 min_exponents 开始的自定义迭代器。 。但这应该作为一个起点。

import itertools

def exponent_partitions(exponents, min_exponents):
    """Generate all vector partitions of 'exponents', each of whose
    entries is lexicographically at least 'min_exponents'."""
    if all(exponent == 0 for exponent in exponents):
        yield []
    else:
        for vector in itertools.product(*(range(v+1) for v in exponents)):
            if vector >= min_exponents:
                remainder = tuple(x - y for x, y in zip(exponents, vector))
                for partition in exponent_partitions(remainder, vector):
                    yield partition + [vector]


def divisor_from_exponents(primes, exponent_vector):
    """Reconstruct divisor from the list of exponents."""
    divisor = 1
    for p, e in zip(primes, exponent_vector):
        divisor *= p**e
    return divisor


def multiplicative_partitions(primes, exponents):
    """Generate all multiplication partitions of
    product(p**e for p, e in zip(primes, exponents))"""
    if len(exponents) == 0:
        # Corner case for partitions of 1.
        yield []
    else:
        initial_vector = (0,) * (len(exponents) - 1) + (1,)
        for partition in exponent_partitions(exponents, initial_vector):
            yield [divisor_from_exponents(primes, vector) for vector in partition]

输出为 24再次:我们正在写24如2**3 * 3**1 ，所以素数元组是 (2, 3)相应的指数元组是 (3, 1) .

>>> for product in multiplicative_partitions((2, 3), (3, 1)):
...     print('*'.join(map(str, product)))
... 
2*2*2*3
4*2*3
8*3
6*2*2
12*2
4*6
24

有大量关于生成和计算整数乘法分区的文献。例如，请参阅 OEIS A001055 中的链接，以及 SAGE functions用于计算向量分区。