सूची की अनुमतियां - हास्केल

मैं 2 सूचियों के साथ उपसमूहों के सभी संभावित संयोजन बनाना चाहता हूं।सूची की अनुमतियां - हास्केल

["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

एक ही विधि का एक सरल संशोधन लौट सकते हैं 3 सूचियों का संयोजन:

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    [[a,b]]

आप इस समारोह के लिए "abc" पार कर लेते हैं, यह इस रिटर्न: यहां एक समारोह है कि सिर्फ इस करता है दो के बजाय।

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    c <- na 
    [[a,b,c]]

एक तर्क के रूप "abc" पास करने का परिणाम:

["aaa","aab","aac","aba","abb","abc","aca","acb","acc", 
"baa","bab","bac","bba","bbb","bbc","bca","bcb","bcc", 
"caa","cab","cac","cba","cbb","cbc","cca","ccb","ccc"]

सबसे आसान तरीका यह सूचियों का एक मनमाना संख्या के पैमाने पर बनाने के लिए क्या है? के रूप में सरल रूप में किया जाता है

replicateM :: Int -> m a -> m [a]

परिभाषा: सूची पर

replicateM n = sequence . replicate n

तो यह sequence है

getCombinations :: Int -> [a] -> [[a]]

स्रोत

2012-01-08 RooSoft

आप हमेशा hoogle का उपयोग करने का प्रयास कर सकते हैं: http://www.haskell.org/hoogle/?hoogle=Int+-%3E+[a]+-%3E+[[a]], यह तीसरे परिणाम के रूप में प्रतिकृति एम देता है। – sdcvvc

धन्यवाद sdcvvc, मुझे नहीं पता था कि होगल की क्वेरी करना संभव था! – RooSoft

तकनीकी रूप से, ये [क्रमपरिवर्तन] (https://en.wikipedia.org/wiki/Permutation) नहीं [संयोजन] (https://en.wikipedia.org/wiki/Combination) हैं। गणितज्ञ पैडेंटिक होंगे ... –

क्या आप चाहते हैं replicateM है: यहाँ क्या प्रकार घोषणा दिखना चाहिए की तरह है मोनैड जो यहां असली काम कर रहा है।

स्रोत

2012-01-08 17:54:03 ehird

यह बिल्कुल ठीक है जिस तरह से मैं देख रहा था। बहुत बहुत धन्यवाद! – RooSoft

@RooSoft आप कुछ भी कम क्यों उम्मीद करेंगे? विशेष रूप से एसओ पर। खासकर [हैकेल] टैग (एसओ पर सबसे दोस्ताना टैग) के लिए। –

आप कितने क्रूर हैं, मुझे इस तरह शर्मिंदा करते हैं। यहां मेरे पास है: '\ i l-> iterate (ap (fmap (:) l)) [[]] !! i' T_T – Rotsor

यहाँ combination समारोह के लिए आने वालों के लिए, एक कश्मीर एक सेट एस की -combination कश्मीरएस के विशिष्ट तत्वों का एक सबसेट है, ध्यान दें कि कोई फर्क नहीं पड़ता।

चुनें n तत्वों से k तत्वों बराबर n - 1 तत्वों से k - 1 तत्वों का चयन प्लस n - 1 तत्वों से k तत्वों चुनें।

enter image description here

उपयोग इस पुनरावर्ती परिभाषा, हम लिख सकते हैं:

combinations :: Int -> [a] -> [[a]] 
combinations k xs = combinations' (length xs) k xs 
    where combinations' n k' [email protected](y:ys) 
      | k' == 0 = [[]] 
      | k' >= n = [l] 
      | null l = [] 
      | otherwise = map (y :) (combinations' (n - 1) (k' - 1) ys) ++ combinations' (n - 1) k' ys 


ghci> combinations 5 "abcdef" 
["abcde","abcdf","abcef","abdef","acdef","bcdef"]

सेशन के सवाल बार-बार होने क्रमपरिवर्तन है, जो कोई पहले से ही एक जवाब दिया है। गैर-बार-बार क्रमपरिवर्तन के लिए, डेटा.लिस्ट से permutations का उपयोग करें।

स्रोत

2014-03-22 11:44:56

सूची की अनुमतियां - हास्केल

उत्तर

संबंधित मुद्दे