1. ホーム
  2. list

[解決済み] Racketで集合を含む集合を見つける方法

2022-02-25 09:11:49

質問

このプログラムには、いくつかの定義があります。ここで注目すべきは、(set-equal? L1 L2), (union S1 S2), (intersect S1 S2)の3つです。

set-equal?では、L1とL2が等しいかどうかをテストする必要があります。2つの集合がまったく同じメンバーを含んでいれば等しいので、次のように呼び出された場合は順序を無視します。 (set-equal? '(1 (2 3)) '((3 2) 1)) が呼び出された場合、それは真を返すはずです。しかし、私のプログラムを実行すると、上記の呼び出しはfalseを返します。

2つの集合の和は、どちらかの集合に現れるすべての要素の集合で、繰り返しのないものです。だから、次のように呼び出すと (union '((1 2 3)) '((3 2 1))) と呼ぶと、((1 2 3)) を返すはずです。しかし、私のプログラムを実行すると、上の呼び出しは((1 2 3) (3 2 1)を返します。

2つの集合の交わりは、両方の集合に現れる要素の集合です。そこで、次のように呼び出すと (intersect '((1 2 3)) '((3 2 1))) を呼ぶと、((1 2 3)) を返すはずです。しかし、上記の呼び出しで私のプログラムを実行すると、()が返されます。

他のテストケースの中には、意図したとおりに動作するものもあります。しかし、すべてがそうではないので、プログラムは全く正しくありません。私はRacketを使い始めたばかりで、少し混乱しています。このような問題をどのように解決すればよいのか、よくわかりません。おそらく別のヘルパー関数が必要だと考えていますが、それは何をするものなのでしょうか?そしてもっと重要なことは、どのようにするのか?

私の問題は、セットが他のセットを含んでいる場合であり、それにどのように対処すればよいのか、正確にはわからないようです。

コードは以下の通りです。

; Tests if x is in L where L is a set, represented as a list
(define (member? x L)
  (if (null? L)
      #f
      (cond
        [(eq? x (car L)) #t]
        (else (member? x (cdr L))
              ))))

; Test whether L1 is a subset of L2
(define (subset? L1 L2)
  (if (null? L1)
      #t
      (and (member? (car L1) L2)
           (subset? (cdr L1) L2)
      )))

; Test whether L1 and L2 are equal
(define (set-equal? L1 L2)
  (and (subset? L1 L2)
       (subset? L2 L1)
  ))

; Join two sets together
(define (union S1 S2)
  (if (null? S1)
      S2
      (cond
        [(member? (car S1)S2) (union (cdr S1)S2)]
        (else (cons (car S1) (union (cdr S1)S2)))
        )))

; Return the intersection of two sets
(define (intersect S1 S2)
  (if (null? S1)
      '()
      (cond
        [(member? (car S1)S2)
         (cons (car S1) (intersect (cdr S1)S2))]
        (else (intersect(cdr S1)S2))
        )))

皆さんの協力に感謝します。ありがとうございました。

解決方法を教えてください。

の定義 set-equal? が使用します。 subset? を両方向に表示させても問題ありません。 あなたの定義では subset?member? を要素と集合の間に置いても問題ありません。

しかし、あなたの定義する member?eq? の間で、たとえそれらの要素がセット(異なる順序のリスト)であってもです。もし、これらのセットが等価であることを意図しているのであれば、その要素間に eq? そして、ネストされた数値の集合に対して新しい関数を定義します。

;; A NestedNumberSet is one of:
;;  - Number
;;  - [Listof NestedNumberSet]
;; where order doesn't matter in the lists

2つ NestedNumberSet は、次のように等しくなります。 nested-number-set=? もし、それらが両方とも数字であり = または、両方とも集合で、かつ set-equal? .

;; nested-number-set=? : NestedNumberSet NestedNumberSet -> Boolean
(define (nested-number-set=? a b)
  (cond [(and (number? a) (number? b)) (= a b)]
        [(and (list? a) (list? b))     (set-equal? a b)]
        [else                          #false]))

を置き換えると eq? を使用しています。 nested-number-set=? を使用すると、希望するネストされたセット-イクオリティの動作が得られるはずです。


追伸:もっと勉強するまでは eq? をコードに組み込んでください。基本的にはポインタの等価性以外の何物でもないので、たとえ (eq? (list 1 2) (list 1 2))#false .