정수의 곱셈 파티션을 찾는 방법은 무엇입니까?

Question

주어진 정수에 대한 곱셈 파티션을 계산하기위한 효율적인 알고리즘을 찾고 있습니다. 예를 들어, 12 대 등의 파티션의 수는 4이다

12 = 12 X 1 = 4 × 3 = 2 × 2 × 3 = 2 × 6 I이위한 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)); 
    } 
} 

Answer 2

같은 끝낼 다음은 곱셈이 수를 추가 할 수의 순열을 찾을?

숫자를 나눌 수있는 모든 숫자를 찾는 것은 O (n)을 필요로합니다.

그런 다음이 세트를 순열하여이 세트의 곱셈으로 숫자를 줄 수있는 모든 가능한 세트를 찾을 수 있습니다.

원래 숫자를 나눌 수있는 모든 숫자 집합을 찾으면 다이나믹 프로그래밍을 통해 숫자를 찾아서 원래 숫자를 얻을 수 있습니다.

Answer 3

물론, 가장 먼저 할 일은 숫자의 소수 요소를 찾는 것입니다. 예를 들어 글로우 코더는 다음과 같이 말했습니다.

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

그럼

1. 각 곱셈위한 k
2. 의 첨가제 파티션을 발견 등가 인 p^k의 곱셈 파티션을 찾을 0 <= k <= a위한 m = n/p^a
3. 의 곱셈 파티션을 발견 말해 m의 파티션은 배포 할 모든 뚜렷한 방법을 찾습니다. a-k 팩터요인
4. 중 33,210 중복 제조 피하기 (제수, 다수) 쌍 목록 (또는 세트)로 곱셈 파티션을 치료하는 편리한 2. 3.

결과를 결합한다.

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은 계승 느린 이전 얻을 물론이 포함 된 두 개의 소수가 (그러나 squarefree 숫자는 여전히 쉽게) 때문에 특히 쉽다. 목록보다는 신중한 조직과 선택으로 더 나은 데이터 구조를 얻을 수 있다고 생각합니다. 아마도 소수점을 지수로 정렬해야하지만, 지수가 가장 높은 지수로 시작해야할지, 가장 낮은).