如何找到任何整数乘法分区？ [英] How to find multiplicative partitions of any integer?

问题描述

我在寻找一个高效的算法计算乘法分区对于任何给定的整数。例如，这样的分区12的数目是4，这是

I'm looking for an efficient algorithm for computing the multiplicative partitions for any given integer. For example, the number of such partitions for 12 is 4, which are

12 = 12×1 = 4×3 = 2×2×3 = 2×6

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

我读过的维基百科文章这一点，但是这并没有真正给我一个算法生成分区（只对这种分区的数量会谈，并说实话，甚至不是很清楚，我！）。

I've read the wikipedia article for this, but that doesn't really give me an algorithm for generating the partitions (it only talks about the number of such partitions, and to be honest, even that is not very clear to me!).

我在看这个问题，需要我来计算乘法分区非常大的数字（> 1十亿），所以我试图想出一个动态规划方法为它（以便找到一个较小的所有可能的分区号可以被重新使用时，较小的数是本身的一个更大的数的一个因素），但是到目前为止，不知道从哪里开始！

The problem I'm looking at requires me to compute multiplicative partitions for very large numbers (> 1 billion), so I was trying to come up with a dynamic programming approach for it (so that finding all possible partitions for a smaller number can be re-used when that smaller number is itself a factor of a bigger number), but so far, I don't know where to begin!

任何想法/提示将AP preciated - ！这不是一个家庭作业的问题，只是一些我试图解决，因为它的似乎的那么有趣。

Any ideas/hints would be appreciated - this is not a homework problem, merely something I'm trying to solve because it seems so interesting!

推荐答案

我会做的就是数字的质因子分解的第一件事。

The first thing I would do is get the prime factorization of the number.

从那里，我可以使一个排列的因素每个子集的，在该迭代乘以剩余因子

From there, I can make a permutation of each subset of the factors, multiplied by the remaining factors at that iteration.

所以，如果你把一个数字，如24，您将获得

So if you take a number like 24, you get

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

重复所有轮（圆为的因素相乘的第一数目的数目），删除重复它们上来

Repeat for all "rounds" (round being the number of factors in the first number of the multiplication), removing duplicates as they come up.

所以，你最终的东西，如

So you end up with something like

// 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));
    }
}

这篇关于如何找到任何整数乘法分区？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！