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

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,9,4] 组合，因为 9 > b

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

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

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, and restrict the

"for largest in ..."

循环以仅查看那些。

要计算数量，请像这样使用上面的内容：

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