获取给出某种产品的所有可能组合的数量

Question

我正在寻找一种算法来计算给出特定产品的所有可能组合的数量。我有一个完美平方列表 [1,4,9,16,..,n]，我有两个值 a, b，其中 a - 我们可以在乘法中使用以获得完美平方的元素数量，b - 最大值例如，如果 a = 3 且 b = 6，则对于完全平方数 36，我们可以有诸如 [1,6,6]、[2,3,6]、[4、 3,3]等等（顺序问题[1,6,6]和[6,6,1]不同）。注意我们不能使用 [1,9,4] 组合，因为 9 > b

我尝试使用 itertools 中的每个完美平方的所有除数的组合，之后我检查了组合的每个乘积，如果 x1 x2 x3 == 36，我在完美平方 = 36 的计数中添加 1。这个算法有效，但它长乘法需要大量时间。

我们能否让它比查看每个完美正方形的每种组合更快？

def get_divisors(n):
    result = []
    for i in range(1, n//2 + 1):
        if n % i == 0:
            result.append(i)
    result.append(n)
    return result
a = 2
b = 3
count = 0
all_squares = [1,4,9]
for i in all_squares:
    divisors = get_divisors(i)
    for r in divisors:
        if r > b:
            divisors.remove(r)
    for j in (itertools.product(divisors, repeat=a)):
        if numpy.prod(j) == i:
            count += 1
print(count)

Answer 1

这是使用递归生成器的最简单的解决方案。没有大于的元素b出现，因为没有考虑过这么大的元素。重复项永远不会出现，因为通过构造，这会产生元素非递增顺序的列表（即，按字典顺序相反的顺序）。

我不知道广场与这有什么关系。该函数不在乎是否target是正方形，并且您似乎没有在编写的内容中使用该属性。

def solve(target, a, b):
    for largest in range(min(target, b), 1, -1):
        result = []
        rem = target
        # Try one or more factors of `largest`, followed by
        # solutions for what remains using factors strictly less
        # than `largest`.
        while not rem % largest and len(result) < a:
            rem //= largest
            assert rem >= 1
            result.append(largest)
            if rem == 1:
                 yield result + [1] * (a - len(result))
            else:
                for sub in solve(rem,
                                 a - len(result),
                                 largest - 1):
                    yield result + sub

然后，例如

>>> for x in solve(36, 3, 6):
...     print(x)
[6, 3, 2]
[6, 6, 1]
[4, 3, 3]
>>> for x in solve(720, 4, 10):
...     print(x)
[10, 9, 8, 1]
[10, 9, 4, 2]
[10, 8, 3, 3]
[10, 6, 4, 3]
[10, 6, 6, 2]
[9, 8, 5, 2]
[9, 5, 4, 4]
[8, 6, 5, 3]
[6, 6, 5, 4]

如果target可以变大，最简单的“优化”是预先计算其所有非单位因子 <= b，并限制循环"for largest in ..."仅查看那些。

要计算数字，请像这样使用上面的代码：

>>> sum(1 for x in solve(36, 3, 6))
3
>>> sum(1 for x in solve(720, 4, 10))
9

编辑

顺便说一句，随着事情的发展，可以通过在开头添加以下内容来节省大量徒劳的搜索：

    if b ** a < target:
        return

然而，这是否会加速或减慢整体速度取决于输入的预期特征。

优化

运行上面的命令：

>>> for x in solve(36, 3, 6):
...     print(x)
[6, 3, 2]
[6, 6, 1]
[4, 3, 3]
>>> for x in solve(720, 4, 10):
...     print(x)
[10, 9, 8, 1]
[10, 9, 4, 2]
[10, 8, 3, 3]
[10, 6, 4, 3]
[10, 6, 6, 2]
[9, 8, 5, 2]
[9, 5, 4, 4]
[8, 6, 5, 3]
[6, 6, 5, 4]

我的盒子花了将近 30 秒。如果我们将函数更改为仅返回计数而不返回解会怎么样？

def solve(target, a, b):
    count = 0
    for largest in range(min(target, b), 1, -1):
        nres = 0
        rem = target
        while not rem % largest and nres < a:
            rem //= largest
            assert rem >= 1
            nres += 1
            if rem == 1:
                count += 1
            else:
                sub = solve(rem,
                            a - nres,
                            largest - 1)
                count += sub
    return count

返回相同的总数，但花费了接近 20 秒的时间。

现在如果我们记住这个函数怎么办？def只需在;之前添加两行即可

import functools
@functools.cache

不会改变结果，但将时间缩短到半秒以下。

>>> solve.cache_info()
CacheInfo(hits=459534, misses=33755, maxsize=None, currsize=33755)

因此，大部分递归调用是已解析调用的重复，并且由隐藏缓存满足，而不执行函数体。OTOH，我们正在为一个包含大约 32K 条目的隐藏字典燃烧内存。

调味。正如评论指出的，记忆递归函数的通常替代方法是进行更深入的思考，提出一种“动态编程”方法，“从下到上”构建可能的结果，通常使用显式列表而不是隐藏的字典。

不过，我不会在这里这样做。它已经比我实际使用的速度快了数千倍;-)

计算规范的排列数

这是代码：

>>> sum(1 for x in solve(36, 3, 6))
3
>>> sum(1 for x in solve(720, 4, 10))
9

计算不同的排列

这可能是您真正想要的。代码更简单，因为它根本不“聪明”，将所有位置完全相同（因此，例如，所有 3 种不同的排列方式都[6, 6, 1]被认为是不同的）。

如果你希望它在你的一生中完成一次跑步，你绝对需要记住这一点;-)

    if b ** a < target:
        return

第二种方法使用原始函数，并应用早期的numperms()代码来推断每个规范解对应于多少个不同的排列。但它并没有受益于缓存，因此速度要慢得多。第一种方式在 CPython 下需要几秒钟，但在 PyPy 下需要 1 秒钟。

当然，在任何使用 itertools 考虑除数的所有可能排列的方法能够计算出如此大的结果之前，宇宙就会结束。

转至DP

出于教学目的，我认为展示动态编程方法也是值得的。这里的结果很容易是最快的，这是典型的 DP 方法。唉，这也是典型的，它需要更多的预先分析。

这很像递归记忆，但是“自下而上”，从最简单的情况开始，然后迭代地将它们构建为更奇特的情况。但我们不会等待运行时递归来找出需要哪些更简单的情况才能获得更好的结果 - 这一切都已提前分析。

在dimple()代码中，b是不变的。剩下的可以看作是一个大数组 中的条目，M[i, a]它给出了将整数表示i为因子乘积的方法的数量a（全部 <= b）。

“row”0: 中只有一个非零条目M[1, 0] = 1。空乘积 (1) 总是可以实现的。

对于第 1 行，我们一步可以获得什么？好吧， 的每个除数都target可以通过除以自身来减少到第 0 行的情况。target因此，第 1 行对于<=的每个除数都有一个非零条目b，值为 1（只有一种方法可以获取它）。

第 2 行？考虑，例如M[6, 2]。6 可以从第 1 行通过 1 乘以 6、或 6 乘以 1、或 2 乘以 3、或 3 乘 2 得到，所以M[6, 2] = M[1, 1] + M[2, 1] + M[3, 1] + M[6, 1] = 4,

等等。通过正确的准备，主循环的主体非常简单。

请注意，每行i的值仅取决于 row i-1，因此不需要保存整个数组。该代码仅保存最近的行，并从中构建下一行。事实上，通常可以“就地”更新到下一行，因此只需要一行的内存。但在这种特殊情况下，我立即没有找到有效的方法来做到这一点。

此外，由于只能target实现 的约数，因此密集的大部分M将由 0 个条目组成。因此，一行被表示为 a defaultdict(int)，因此仅需要非零条目的存储。

这里的大部分代码都在实用程序中，用于预先计算可能的除数。

编辑：甚至在外循环开始之前就通过预先计算不变量来简化内循环。

>>> sum(1 for x in solve(720000000000, 20, 10000))
4602398

请注意，所需的内存量与 的除数数量成正比target，并且与 无关a。当记忆递归函数时，缓存永远不会忘记任何东西（除非您自己“手动”实现和管理它）。