如果我有一个素数/指数的列表，如何生成一个数的所有乘法分区？

Question

例如，24的素数因式分解为2^3*3^1，可以用以下方式编写

1*24
2*12
2*2*6
2*3*4
2*2*2*3
3*8
4*6

我可能错过了一个，但你明白了。在

我试着去看另一条线索，但不能完全理解答案。在

我不需要任何人来为我编写代码，但是我真的需要一些帮助来创建一个有效的算法（可能是递归的？）。在

我用Python编写代码。在

Answer 1

您的问题可以归结为找到所有的partitions of a set，因为每个因子（素数和复合）都可以表示为组成分区的子集元素的乘积。在

我将用一个列表[2, 2, 2, 3]（好吧，一个集合）来表示你数字的因子。以下是此列表的一些可能分区：

• [2] + [2, 2, 3]
• [2, 2] + [2, 3]
• [2] + [2] + [2, 3]
• [3] + [2] + [2, 2]
• 。。。在

如果将每个子集的每个元素相乘，将得到原始数的因子：

• 2 * 12
• 4 * 6
• 2 * 2 * 6
• 3 * 2 * 4

您可能需要为1 * n添加一个特殊情况。在

这里有一个相关的问题：How can I maximally partition a set?

以及另一个相关链接：Generating the Partitions of a Set