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

Question

我正在寻找一种有效的算法来计算任何给定整数的乘法分区。例如，12的此类分区的数量为4，即

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

我已阅读wikipedia 文章 为此，但这并没有真正给我一个生成分区的算法（它只讨论了这样的分区的数量，说实话，我也不是很清楚！）。

我正在研究的问题要求我计算非常大的数字（> 10亿）的乘法分区，因此我试图为此提出一种动态编程方法（以便找到较小数字的所有可能分区）当较小的数字本身是较大数字的因子时被重新使用），但到目前为止，我不知道从哪里开始！

任何想法/提示将不胜感激 - 这不是一个家庭作业问题，只是我试图解决的问题，因为它看起来非常有趣！

Answer 1

当然，首先要做的是找到数字的质因数分解，就像glowcoder所说的那样。说

n = p^a * q^b * r^c * ...

然后

1. 找到m = n / p^a的乘法分区
2. 对于0 <= k <= a，找到p^k的乘法分区，相当于为
3. m的每个乘法分区找到k的加法分区，找到分配ak的所有不同方式因素
4. 组合 中的因素p 2.和3的结果。

将乘法分区视为（除数，重数）对的列表（或集合）以避免产生重复是很方便的。

我用 Haskell 编写了代码，因为它是我所知道的处理此类事情的语言中最方便、最简洁的：

module MultiPart (multiplicativePartitions) where

import Data.List (sort)
import Math.NumberTheory.Primes (factorise)
import Control.Arrow (first)

multiplicativePartitions :: Integer -> [[Integer]]
multiplicativePartitions n
    | n < 1     = []
    | n == 1    = [[]]
    | otherwise = map ((>>= uncurry (flip replicate)) . sort) . pfPartitions $ factorise n

additivePartitions :: Int -> [[(Int,Int)]]
additivePartitions 0 = [[]]
additivePartitions n
    | n < 0     = []
    | otherwise = aParts n n
      where
        aParts :: Int -> Int -> [[(Int,Int)]]
        aParts 0 _ = [[]]
        aParts 1 m = [[(1,m)]]
        aParts k m = withK ++ aParts (k-1) m
          where
            withK = do
                let q = m `quot` k
                j <- [q,q-1 .. 1]
                [(k,j):prt | let r = m - j*k, prt <- aParts (min (k-1) r) r]

countedPartitions :: Int -> Int -> [[(Int,Int)]]
countedPartitions 0     count = [[(0,count)]]
countedPartitions quant count = cbParts quant quant count
  where
    prep _ 0 = id
    prep m j = ((m,j):)
    cbParts :: Int -> Int -> Int -> [[(Int,Int)]]
    cbParts q 0 c
        | q == 0    = if c == 0 then [[]] else [[(0,c)]]
        | otherwise = error "Oops"
    cbParts q 1 c
        | c < q     = []        -- should never happen
        | c == q    = [[(1,c)]]
        | otherwise = [[(1,q),(0,c-q)]]
    cbParts q m c = do
        let lo = max 0 $ q - c*(m-1)
            hi = q `quot` m
        j <- [lo .. hi]
        let r = q - j*m
            m' = min (m-1) r
        map (prep m j) $ cbParts r m' (c-j)

primePowerPartitions :: Integer -> Int -> [[(Integer,Int)]]
primePowerPartitions p e = map (map (first (p^))) $ additivePartitions e

distOne :: Integer -> Int -> Integer -> Int -> [[(Integer,Int)]]
distOne _ 0 d k = [[(d,k)]]
distOne p e d k = do
    cap <- countedPartitions e k
    return $ [(p^i*d,m) | (i,m) <- cap]

distribute :: Integer -> Int -> [(Integer,Int)] -> [[(Integer,Int)]]
distribute _ 0 xs = [xs]
distribute p e [(d,k)] = distOne p e d k
distribute p e ((d,k):dks) = do
    j <- [0 .. e]
    dps <- distOne p j d k
    ys <- distribute p (e-j) dks
    return $ dps ++ ys
distribute _ _ [] = []

pfPartitions :: [(Integer,Int)] -> [[(Integer,Int)]]
pfPartitions [] = [[]]
pfPartitions [(p,e)] = primePowerPartitions p e
pfPartitions ((p,e):pps) = do
    cop <- pfPartitions pps
    k <- [0 .. e]
    ppp <- primePowerPartitions p k
    mix <- distribute p (e-k) cop
    return (ppp ++ mix)

它不是特别优化的，但它可以完成工作。

有时和结果：

Prelude MultiPart> length $ multiplicativePartitions $ 10^10
59521
(0.03 secs, 53535264 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^11
151958
(0.11 secs, 125850200 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^12
379693
(0.26 secs, 296844616 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 10]
70520
(0.07 secs, 72786128 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 11]
425240
(0.36 secs, 460094808 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 12]
2787810
(2.06 secs, 2572962320 bytes)

10^k 当然特别简单，因为只涉及两个素数（但无平方数仍然更容易），阶乘较早变慢。我认为通过仔细组织顺序并选择比列表更好的数据结构，可以获得相当多的收获（可能应该按指数对素因数进行排序，但我不知道是否应该从最高指数开始或最低）。

Answer 2

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

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

因此，如果您采用像 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));
    }
}

Answer 3

为什么你不找到所有可以整除该数字的数字，然后找到乘法将加起来等于该数字的数字的排列？

找到所有能整除你的数字需要 O(n) 的时间。

然后你可以排列这个集合来找到所有可能的集合，该集合的乘法将给你这个数字。

一旦找到了除原始数字的所有可能数字的集合，那么您可以对它们进行动态编程，以找到将它们相乘得到原始数字的数字集合。