فئات التكافؤ lisp

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

هذا يبدو وكأنه سؤال منزلي نموذجي.

هذا ليس بالأمر الصعب ، رغم ذلك.

ستفعل وظيفة متكررة بسيطة على قائمة الإدخال. تم ذكر مكونات الوظيفة بالفعل في وصف المهمة: عمليات تعيين بسيطة.

إذا كانت الواجب المنزلي ، فهذا ينطبق: الاستراتيجية النموذجية لأسئلة الواجب المنزلي هي أنه يتعين عليك إظهار محاولة الحلول أولاً. يجب أن يكون ذلك على الأقل صياغة صحيحة في الغالب للخوارزمية أو رمز العمل تقريبًا. ثم قد يساعدك Lispers في اللمسات النهائية ...

حسنا ، الوقت يمر ولا حل.

إذن هنا يستخدم LISP المشترك:

نحن بحاجة إلى ثلاث وظائف.

تضيف الوظيفة الأولى زوجًا واحدًا إلى مجموعة الأزواج. الزوج هو قائمة. مجموعة الأزواج هي قائمة الأزواج. بالنسبة للزوج ، نحسب مجموعتين: مجموعة الأزواج المكافئة ومجموعة الأزواج غير المتكافئة. نحن نجمع بين الأزواج المكافئة مع زوج الإدخال لدينا في مجموعة واحدة.

(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-)))

تضيف الوظيفة الثانية كل زوج من مجموعة الأزواج إلى النتيجة. يضيفهم عن طريق استدعاء equiv-add.

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

الوظيفة الثالثة فقط تستدعي equiv-aux مع مجموعة الإدخال ونتيجة فارغة. بالإضافة إلى ذلك فصحيف النتيجة.

(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))