तुल्यता वर्ग तुतलाना

Question

मैं तुल्यता कक्षाओं के लिए एक प्रोग्राम लिखने और इस आउटपुट प्राप्त करने की आवश्यकता ...

(equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
=> ((a b c g h) (d e f)) 

(equiv '((a b) (c d) (e f) (f g) (a e))) 
=> ((a b e f g) (c d)) 

असल में, एक सेट एक सूची है, जिसमें आदेश कोई फर्क नहीं पड़ता है, लेकिन तत्वों नहीं है एक से अधिक बार प्रकट होते हैं। फ़ंक्शन को जोड़े की एक सूची (तत्व जो कुछ समकक्ष संबंध के अनुसार संबंधित हैं) स्वीकार करते हैं, और पुनरावृत्ति या असाइनमेंट स्टेटमेंट (उदाहरण के लिए do, set! इत्यादि) के बिना समकक्ष वर्गों का एक सेट वापस कर सकते हैं।

हालांकि, सेट उपयोगिताओं set-intersection जैसे, set-union और एक समारोह जो किसी सूची में डुप्लिकेट और बिल्ट-इन कार्य union, intersection समाप्त, और remove-duplicates अनुमति दी जाती है।

बहुत बहुत धन्यवाद!

वैसे, यह होमवर्क प्रश्न नहीं है। मेरे एक दोस्त को स्माइलर सवालों को हल करने के लिए कोड के इस टुकड़े की आवश्यकता है।

Answer 1

यह एक सामान्य होमवर्क प्रश्न की तरह लगता है।

हालांकि यह मुश्किल नहीं है।

इनपुट सूची पर एक सरल पुनरावर्ती कार्य करेगा। कार्य विवरण में पहले से ही कार्य विवरण में वर्णित हैं: सरल सेट ऑपरेशंस।

यदि यह होमवर्क है, तो यह लागू होता है: होमवर्क प्रश्नों के लिए सामान्य रणनीति यह है कि आपको अपना समाधान प्रयास पहले दिखाना है। यह कम से कम एल्गोरिदम या लगभग काम करने वाले कोड का सही रूप से सही फॉर्मूलेशन होना चाहिए। फिर लिस्पर्स आपको अंतिम छूने में मदद कर सकते हैं ...

ठीक है, समय बीतता है और कोई समाधान नहीं है।

तो यहाँ एक कॉमन लिस्प उपयोग कर रहा है:

हम तीन कार्यों की जरूरत है।

पहला फ़ंक्शन जोड़ों के सेट में एक जोड़ी जोड़ता है। एक जोड़ी एक सूची है। जोड़े का सेट जोड़े की एक सूची है। जोड़ी के लिए हम दो सेटों की गणना करते हैं: जोड़े के सेट जो बराबर हैं और जोड़े के सेट जो बराबर नहीं हैं। हम उन जोड़ों को गठबंधन करते हैं जो हमारे इनपुट इनपुट जोड़ी के साथ एक सेट में बराबर हैं।

(defun equiv-add (e l) 
    (let ((l- (remove-if  (lambda (i) (intersection e i)) l)) 
     (l+ (remove-if-not (lambda (i) (intersection e i)) l))) 
    (cons (remove-duplicates (reduce #'union (cons e l+))) 
      l-))) 

दूसरा फ़ंक्शन परिणामों के जोड़े के प्रत्येक जोड़े को परिणाम में जोड़ता है। यह उन्हें इक्विव-एडीडी कॉल करके जोड़ता है।

(defun equiv-aux (list result) 
    (if (null list) 
     result 
    (equiv-aux (rest list) 
       (equiv-add (first list) 
          result)))) 

तीसरे समारोह सिर्फ इनपुट सेट और एक खाली परिणाम के साथ समतुल्य-aux कहता है। इसके अतिरिक्त यह परिणाम sublists का प्रकार है।

(defun equiv (list) 
    (mapcar (lambda (el) 
      (sort el #'string-lessp)) 
      (equiv-aux list '()))) 

उदाहरण कॉल:

CL-USER 34 > (equiv '((a b) (c d) (e f) (f g) (a e))) 
((A B E F G) (C D)) 

CL-USER 35 > (equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
((A B C G H) (D E F))