किसी भी पूर्णांक के गुणात्मक विभाजन कैसे प्राप्त करें?

Question

मैं किसी दिए गए पूर्णांक के लिए गुणात्मक विभाजन की गणना करने के लिए एक कुशल एल्गोरिदम खोज रहा हूं। उदाहरण के लिए, 12 के लिए इस तरह के विभाजन की संख्या 4, जो कर रहे हैं है

12 = 12 एक्स 1 = 4 x 3 = 2 एक्स 2 एक्स 3 = 2 एक्स 6

मैं इसके लिए wikipedia article पढ़ा है , लेकिन यह वास्तव में विभाजन को उत्पन्न करने के लिए मुझे एल्गोरिदम नहीं देता है (यह केवल ऐसे विभाजनों की संख्या के बारे में बात करता है, और ईमानदार होने के लिए, यहां तक ​​कि यह मेरे लिए बहुत स्पष्ट नहीं है!)।

जिस समस्या को मैं देख रहा हूं, मुझे बहुत बड़ी संख्या (> 1 अरब) के लिए गुणात्मक विभाजन की गणना करने की आवश्यकता है, इसलिए मैं इसके लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण के साथ आने की कोशिश कर रहा था (ताकि एक के लिए सभी संभावित विभाजन ढूंढ सकें छोटी संख्या का फिर से उपयोग किया जा सकता है जब वह छोटा नंबर स्वयं एक बड़ी संख्या का कारक होता है), लेकिन अब तक, मुझे नहीं पता कि कहां से शुरू करना है!

कोई भी विचार/संकेत की सराहना की है - यह नहीं एक होमवर्क समस्या है, केवल कुछ मैं क्योंकि यह इतना दिलचस्प लगता है हल करने के लिए कोशिश कर रहा हूँ है!

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

कुछ के साथ खत्म आप सभी नंबरों को उस नंबर विभाजित कर सकते हैं क्यों लगता है न और फिर आप संख्याओं को गुणा संख्या तक जोड़ देगा के क्रमपरिवर्तन पाते हैं?

आपकी संख्या को विभाजित करने वाले सभी नंबरों को ढूंढना ओ (एन) लेता है।

फिर आप इस सेट को सभी संभावित सेट खोजने के लिए अनुमति दे सकते हैं कि इस सेट के गुणा से आपको संख्या मिल जाएगी।

एक बार जब आप मूल संख्या को विभाजित करने वाले सभी संभावित संख्याओं का सेट प्राप्त कर लेते हैं, तो आप उन्हें गुणा करने वाले नंबरों के सेट को खोजने के लिए गतिशील प्रोग्रामिंग कर सकते हैं जो आपको मूल संख्या देगा।

Answer 3

बेशक, पहली बात यह है कि संख्या का मुख्य कारक है, जैसे ग्लोकोडर ने कहा।

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

फिर

1. 0 <= k <= a के लिए m = n/p^a
2. के गुणक विभाजन मिल जाए, जो प्रत्येक गुणक के लिए k
3. के additive विभाजन पाने के लिए बराबर है p^k के गुणक विभाजन मिल जाए, कहो m का विभाजन, a-k कारकों को वितरित करने के सभी विशिष्ट तरीके खोजेंकारकों
4. के बीचके 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 संख्या अब भी आसान होता है) कर रहे हैं, factorials धीमी गति से पहले मिलता है। मुझे सूचियों की तुलना में बेहतर डेटा संरचनाओं के आदेश और पसंद के सावधान संगठन द्वारा लगता है, प्राप्त करने के लिए काफी कुछ है (शायद किसी को एक्सपोनेंट द्वारा प्रमुख कारकों को सॉर्ट करना चाहिए, लेकिन मुझे नहीं पता कि किसी को उच्चतम घाटियों के साथ शुरू करना चाहिए या नहीं सबसे कम)।