给定除数列表中的数字的高效逆因式分解

Question

给定一个数字n和一个除数列表A，我如何有效地找到乘以该数字时产生的所有除数组合？例如n = 12 A = [2, 3, 4]输出：[[3, 2, 2], [2, 3, 2], [2, 2, 3], [4, 3], [3, 4]]这是我到目前为止所做的（代码是我根据 stackoverflow 上的许多查找质因数分解问题之一重新改编的）：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]@Memoizedef 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

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

要实现这一点，A应该进行排序。

第1部分：

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

                   12

                /  |  \

               /   |   \

              /    |    \

          2(x6)  3(x4)   4(x3)

         /  |      |  \

     2(x3) 3(x2)   3   4(x1)

    /  |

   2  3(x1)

粗体节点是导致成功分解的路径。罢工节点是导致冗余分支的节点，因为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)))

您可以将其放入productsas的最后一行

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 毫秒 vs 42 毫秒。

第 2b 部分：

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

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 与 4.9μs，长示例的时间为 6.5ms 与 42ms。事实上，如果有的话，避免重复排列似乎可以进一步减少时间。

长话短说

一种更高效的实现，仅使用标准库并仅搜索唯一因式分解的唯一排列：

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, [])))