Return Python 中数字列表的不同乘法组合

Question

我有一个数字列表，我希望 return 一个二维列表，最好是从最大到最小排序（虽然我可以在之后这样做），所有可能的乘法组合（产生原始列表的产品）使用列表的所有元素，没有重复项。也就是说，如果我有 [1, 2, 3] 的列表，我希望它 return

[[3, 2, 1], [3, 2], [6, 1], [6]]

没有重复项或等效列表，如上所示（[2,3] 未出现）。

这样做的原因是找到所有将一个数的质因数相乘的方法。也就是从24的质因数(2, 2, 2, 3) 我要return

[[3, 2, 2, 2], [4, 3, 2], [6, 4], [6, 2, 2], [8, 3], [12, 2], [24]]

我希望我已经说清楚了，我不确定如何正确表达这个问题。

Answer 1

您可以这样做的一种方法是：使用两个嵌套循环将列表中的每个数字与其他数字相乘，然后在新列表上递归。这不是很有效，因为您将有大量重复的函数调用（例如，将 (3, 2, 2, 2) 中的 3 与三个 2 中的任何一个相乘，但这可以通过一点记忆（不幸的是，这意味着我们必须在列表和元组之间进行大量转换）。不过，对于较大的输入，它不是很快。

def memo(f):
    f.cache = {}
    def _f(*args, **kwargs):
        if args not in f.cache:
            f.cache[args] = f(*args, **kwargs)
        return f.cache[args]
    return _f

@memo
def mult_comb(factors):
    result = set()
    result.add(tuple(sorted(factors)))
    for i, f1 in enumerate(factors):
        factors2 = list(factors[:i] + factors[i+1:])
        for k in range(i, len(factors2)):
            factors2[k] *= f1
            result.update(mult_comb(tuple(factors2)))
            factors2[k] /= f1
    return result

示例：

>>> mult_comb((3,2,2,2))
set([(4, 6), (3, 8), (2, 12), (2, 3, 4), (24,), (2, 2, 6), (2, 2, 2, 3)])

Return Python 中数字列表的不同乘法组合

Return the different multiplicative combinations of a list of numbers in Python

python

combinations