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

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

您的问题可以缩减为查找集合的所有分区,因为每个因子(素数和复合)都可以表示为构成分区的子集元素的乘积.

我会将你的号码因素表示为一个列表[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.

这是一个相关的问题:我如何最大限度地划分一组？

另一个相关链接:生成集合的分区