给定除数列表的数字的有效反向分解

Question

给定一个数字 n 和一个除数列表 A，我如何才能有效地找到所有除数的组合，这些组合在相乘时会产生该数字？

例如

n = 12 
A = [2, 3, 4]

输出：

[[3, 2, 2],
 [2, 3, 2],
 [2, 2, 3],
 [4, 3],
 [3, 4]]

这是我到目前为止设法做到的（我从 Whosebug 上的许多 find-prime-factorization 问题之一重新改编的代码）：

def products(n, A):
    if n == 1:
        yield []
    for each_divisor in A:
        if n % each_divisor == 0:
            for new_product in products(n // each_divisor, A):
                yield new_product + [each_divisor]

这段代码似乎可以正常工作，但速度很慢，如果我尝试使用记忆（将 A 作为元组传递给函数以避免不可散列的类型错误），代码不会提供正确的结果。

关于如何提高这段代码的效率有什么建议吗？

我试过的记忆代码如下：

class Memoize:
    def __init__(self, fun):
        self.fun = fun
        self.memo = {}

    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fun(*args)
        return self.memo[args]

@Memoize
def products(n, A): [as above]

当用上面定义的参数调用函数时n, A:

>>> list(products(12, (2, 3, 4)))
[[3, 2, 2]]

没有记忆，相同代码的输出是：

[[3, 2, 2], [2, 3, 2], [2, 2, 3], [4, 3], [3, 4]]

请注意，其他记忆功能（例如 functools 包 @functools.lru_cache(maxsize=128) 中的）也会导致同样的问题。

Answer 1

您可以将问题拆分为一个递归部分以查找所有唯一组合，以及一个部分以查找每个排列的组合，而不是使用记忆。这应该会大大减少您的搜索 space，并且只会排列实际有效的选项。

为此，A 应该排序。

第 1 部分：

对可用的可能因式分解图进行 DFS。通过仅选择每个因子大于或等于其前一个因子的顺序来截断冗余分支的搜索。例如：

                   12
                /  |  \
               /   |   \
              /    |    \
          2(x6)  3(x4)   4(x3)
         /  |      |  \
     2(x3) 3(x2)   3   4(x1)
    /  |
   2  3(x1)

Bold 节点是导致成功分解的路径。 ~~Struck~~节点是导致冗余分支的节点，因为除以该因子后剩余的n小于该因子。没有在括号中显示剩余值的节点根本不会导致因式分解。对于低于当前因素的因素，不尝试分支：当我们尝试 3 时，永远不会重新访问 2，只有 3 和 4，等等

在代码中：

A.sort()

def products(n, A):
    def inner(n, A, L):
        for i in range(len(A)):
            factor = A[i]
            if n % factor: continue

            k = n // factor
            if k < factor:
                if k == 1:
                    yield L + [factor]
                elif n in A:
                    yield L + [n]
                break  # Following k guaranteed to be even smaller
                       # until k == 1, which elif shortcuts

            yield from inner(k, A[i:], L + [factor])

    yield from inner(n, A, [])

这相当快。在您的特定情况下，它只检查 4 个节点而不是 ~30 个。事实上，您可以证明它检查了可能的绝对最小节点数。您可能获得的唯一改进是使用迭代而不是递归，我怀疑这会有多大帮助。

第 2 部分：

现在，您只需生成结果的每个元素的排列。 Python 提供了直接在标准库中执行此操作的工具：

from itertools import chain, permutations

chain.from_iterable(map(permutations, products(n, A)))

您可以将其放入 products 的最后一行，如

yield from chain.from_iterable(map(permutations, inner(n, A, [])))

运行 list(products(12, A)) 以这种方式显示我的机器有 20-30% 的改进（5.2µs 对比 4.0µs）。运行更复杂的示例 list(products(2 * 3 * 4 * 5 * 5 * 7 * 11, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 22])) 显示了更显着的改进：7 毫秒对 42 毫秒。

第 2b 部分：

您可以使用类似于显示的方法 here（无耻插件）过滤掉由于重复因素而发生的重复排列。适应我们总是处理排序整数的初始列表这一事实，它可以写成这样：

def perm_dedup(tup):
    maximum = (-1,) * len(tup)
    for perm in permutations(tup):
        if perm <= maximum: continue
        maximum = perm
        yield perm

现在您可以在最后一行使用以下内容：

yield from chain.from_iterable(map(perm_dedup, inner(n, A, [])))

时间仍然非常有利于这种完整的方法：问题 5.2µs vs 4.9µs，长示例 6.5ms vs 42ms。事实上，如果有的话，避免重复排列似乎可以进一步减少时间。

TL;DR

仅使用标准库并仅搜索唯一分解的唯一排列的更有效的实现：

from itertools import chain, permutations

def perm_dedup(tup):
    maximum = (-1,) * len(tup)
    for perm in permutations(tup):
        if perm <= maximum: continue
        maximum = perm
        yield perm

def products(n, A):
    A = sorted(set(A))
    def inner(n, A, L):
        for i in range(len(A)):
            factor = A[i]
            if n % factor: continue

            k = n // factor
            if k < factor:
                if k == 1:
                    yield L + [factor]
                elif n in A:
                    yield L + [n]
                break  # Following k guaranteed to be even smaller
                       # until k == 1, which elif shortcuts

            yield from inner(k, A[i:], L + [factor])

    yield from chain.from_iterable(map(perm_dedup, inner(n, A, [])))

给定除数列表的数字的有效反向分解

Efficient reverse-factorization of a number given list of divisors

python

recursion

permutation

factorization