algorithm - 如何找到任何整数的乘法分区？

Question

我正在寻找一种有效的算法来计算任何给定整数的乘法分区。比如12这样的分区数是4个，分别是

12 = 12 x 1 = 4 x 3 = 2 x 2 x 3 = 2 x 6

我读过 wikipedia article为此，但这并没有真正给我一个生成分区的算法(它只讨论了这样的分区的数量，老实说，即使这对我来说也不是很清楚!)。

我正在研究的问题要求我计算非常大的数字(> 10 亿)的乘法分区，所以我试图为它想出一个动态编程方法(以便为较小的数字找到所有可能的分区当较小的数字本身是较大数字的一个因素时，数字可以重复使用)，但到目前为止，我不知道从哪里开始!

任何想法/提示都将不胜感激 - 这不是家庭作业问题，只是我正在尝试解决的问题，因为它似乎非常有趣!

Answer 1

我要做的第一件事是对数字进行质因数分解。

从那里，我可以对因子的每个子集进行排列，并乘以该迭代中的其余因子。

所以如果你取一个像 24 这样的数字，你会得到

2 * 2 * 2 * 3 // prime factorization
a   b   c   d
// round 1
2 * (2 * 2 * 3) a * bcd
2 * (2 * 2 * 3) b * acd (removed for being dup)
2 * (2 * 2 * 3) c * abd (removed for being dup)
3 * (2 * 2 * 2) d * abc

重复所有“轮次”(轮次是乘法第一个数字中的因子数)，删除出现的重复项。

所以你最终会得到类似的东西

// assume we have the prime factorization 
// and a partition set to add to
for(int i = 1; i < factors.size; i++) {
    for(List<int> subset : factors.permutate(2)) {
        List<int> otherSubset = factors.copy().remove(subset);
        int subsetTotal = 1;
        for(int p : subset) subsetTotal *= p;
        int otherSubsetTotal = 1;
        for(int p : otherSubset) otherSubsetTotal *= p;
        // assume your partition excludes if it's a duplicate
        partition.add(new FactorSet(subsetTotal,otherSubsetTotal));
    }
}