सूची समझ: सूचियों की सूचियां बनाना

Question

नमस्ते मैं हैकेल में एक फ़ंक्शन बनाने की कोशिश कर रहा हूं जो संख्या 4 के लिए सूचियों का उपयोग करके इसका एक हिस्सा बनाता है, यह [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]] बनाएगा। मैं इस के लिए सूची समझ का उपयोग करने के बारे में सोच रहा था, जहां यह सूची एक्स बनायेगा और फिर [1 ... n] से संख्याओं का उपयोग करके और सूचियां बनायेगा (n विभाजन संख्या जो मैं चाहता हूं) जहां बनाई गई सूची का योग बराबर होगा एन के लिए

कोड मैं अब तक है-

partions (n:xs) = [[x|x<-[1...n], sum[x]==n]]|xs<-[1..]] 

बनाया है लेकिन obiviously यह does not काम, किसी भी सुझाव?

धन्यवाद।

Answer 1

मैं पुनरावृत्ति की कोशिश करने का सुझाव देता हूं: एन के विभाजन प्राप्त करने के लिए, I = 1 से n संख्याओं पर पुनरावृत्त करें, और (ni) के विभाजन को पुन: उत्पन्न करें, मूल मामला यह है कि 1 का एकमात्र विभाजन 1 है, और 0 का विभाजन खाली सूची है।

Answer 2

मैं हास्केल के साथ थोड़ा जंगली हूँ, लेकिन हो सकता है कि निम्न कोड आपको समाधान ढूंढने के लिए मार्गदर्शन कर सके।

parts :: Int -> Int -> [[Int]] 
parts 0 p = [[]] 
parts x p = [(y:ys) | y <-[p..x], ys <- (parts (x - y) y)] 

और फिर आप के साथ एक्स = n, और पी = 1.

संपादित

मैं आधार मामले को सुलझा लिया है जब एक्स एक वापस करने के लिए 0 के बराबर होती है भागों फोन करने के लिए होगा एक आइटम के साथ सूची, उस आइटम को एक खाली सूची है। अब यह ठीक काम करता है :)

Answer 3

कैसे इस बारे में ...

import Data.List (nub, sort) 

parts :: Int -> [[Int]] 
parts 0 = [] 
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)] 

यह कोशिश कर रहा है:

*Main Control.Monad> forM [1..5] (print . parts) 
[[1]] 
[[2],[1,1]] 
[[3],[1,2],[1,1,1]] 
[[4],[1,3],[1,1,2],[1,1,1,1],[2,2]] 
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[2,3]] 

मुझे लगता है कि यह सही है, यदि कुशल नहीं।

Answer 4

मुझे एक सहायक फ़ंक्शन, partitionsCap परिभाषित करने में मदद मिली, जो किसी भी आइटम को दिए गए मान से बड़ा नहीं होने देता है। रिकर्सिवली प्रयुक्त, यह केवल करने के लिए इस्तेमाल किया जा सकता monotonically परिणाम घटते आप चाहते हैं का उत्पादन (यानी कोई [1,3,1] आप पहले से ही [1,1,3] है जब):

partitions :: Int -> [[Int]] 
partitions n = partitionsCap n n 

partitionsCap :: Int -> Int -> [[Int]] 
partitionsCap cap n 
    | n < 0 = error "partitions: negative number" 
    | n == 0 = [[]] 
    | n > 0 = [i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
       where hi = min cap n 

---

एल्गोरिथ्म के केंद्र में विचार है कि, जब विभाजन है एन, n से 1 तक नीचे ले जाएं, और n-i के विभाजन में i प्रीपेड करें। सरलीकृत:

concat [map (i:) $ partitions (n-i) | i <- [n,n-1..1]] 

लेकिन गलत:

> partitions 3 
[[3],[2,1],[1,2],[1,1,1]] 

हम उस [1,2] दूर जाना चाहते हैं।इसलिए, हम i ऊपर विभाजन हम तो वे नहीं जाना होगा करने के लिए prepending रहे हैं टोपी की जरूरत है: अब

concat [map (i:) $ partitionsCap i (n-i) | i <- [hi,hi-1..1]] 
where hi = min cap n 

, यह साफ करने के लिए ऊपर: कि concat और नक्शा इतने करीब एक साथ मेरा ध्यान मिल गया । एक छोटी सी पृष्ठभूमि: सूची की समझ और सूची मोनड very closely related हैं, और concatMap>>= जैसा ही है, इसके मोनैड सूची में, इसके तर्क फ़्लिप किए गए हैं। तो मैंने सोचा: क्या concat और मानचित्र किसी भी तरह >>= में बदल सकता है, और क्या >>= किसी भी तरह से सूची समझ में अपना रास्ता मिल सकता है?

इस मामले में, जवाब है हां

[i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
where hi = min cap n