14

任意の整数の乗法的分割を計算するための効率的なアルゴリズムを探しています。たとえば、12のそのようなパーティションの数は4であり、

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

私はこれについてウィキペディアの記事を読みましたが、それは実際にはパーティションを生成するためのアルゴリズムを私に与えません（それはそのようなパーティションの数についてのみ話します、そして正直なところ、それは私にはあまり明確ではありません！） 。

私が見ている問題では、非常に大きな数（> 10億）の乗法的分割を計算する必要があるため、動的計画法のアプローチを考え出そうとしていました（これにより、少数の可能なすべてのパーティションを見つけることができます。その小さい数自体が大きい数の要因である場合に再利用されます）が、これまでのところ、どこから始めればよいのかわかりません！

どんなアイデア/ヒントもいただければ幸いです。これは宿題の問題ではなく、とても面白そうなので、私が解決しようとしていることです。

4

3 に答える 3

6

私が最初にすることは、数の素因数分解を取得することです。

そこから、因子の各サブセットの順列を作成し、その反復で残りの因子を掛けることができます。

したがって、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));
    }
}
于 2011-12-19T07:33:04.903 に答える
5

もちろん、最初にすべきことは、グローコーダーが言ったように、数の素因数分解を見つけることです。言う

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

それで

  1. の乗法的分割を見つけるm = n / p^a
  2. の場合0 <= k <= a、の乗法的分割を見つけますp^k。これは、の加法的分割を見つけることと同じです。k
  3. の乗法的分割ごとに、因子間で因子mを分散するためのすべての異なる方法を見つけますa-kp
  4. 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関係する素数は2つしかないため（ただし、平方因子をもたた数の方が簡単です）、階乗は早く遅くなります。リストよりも優れたデータ構造の順序と選択を注意深く整理することで、得られるものはかなりあると思います（おそらく、素因数を指数で並べ替える必要がありますが、最も高い指数から始めるか、最も低い）。

于 2011-12-21T03:41:29.257 に答える
0

数を割ることができるすべての数を見つけて、乗算が数に加算される数の順列を見つけないのはなぜですか？

あなたの数を割ることができるすべての数を見つけることはO（n）を取ります。

次に、このセットを並べ替えて、このセットを乗算すると数値が得られる可能性のあるすべてのセットを見つけることができます。

元の数を除算する可能性のあるすべての数のセットを見つけたら、それらに対して動的計画法を実行して、それらを乗算すると元の数が得られる数のセットを見つけることができます。

于 2011-12-19T07:34:51.513 に答える