3

same?を返す述語#tを作成するにはどうすればよい(same? '(4 6) '(6 4))ですか? とが等しいセットであるか、そうでないか(same? a b)を返す述語を書くことに行き詰まっています。また、が の要素であるかどうかを判断する同様の述語です。#tab#f(element? el set)elset

（そして、はい、これは宿題なので、完全に完成した解決策を求めているわけではありません。先生からの助けはほとんどないので、正しい方向に少しでもぶつかる必要があるだけです。）

リストを使って集合を表現しています。私たちは、これに必要なものをすべて自分たちで構築するよう求められています。map などの高次関数はほとんど禁止されています。

問題は、私の要素ですか？そして同じ？以下では動作しません:

(same? '(4 6) '(6 4))<br/>
(element? '(2 3) '(1 8 5 '(3 2) 4))

これらは返されるはず#tですが、そうではありません。理由は理解できますが、まだ修正できません。

私のelement?見た目はこのようで、同じ順序のリストでしか機能しないことはわかっていましたが、問題はどうすれば改善できるでしょうか? ( setEmpty、setFirst、は 、 、とsetRest定義されています。何らかの理由で独自のものを作成するように求められています。)null?carcdr

(define element?
  (lambda (x set)
     (cond ((setEmpty? set) #f)
      ((equal? x (setFirst set)) #t)
      (else (element? x (setRest set)))
      )
   )
)

私は次のset?ように機能する述語を持っています。

(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
          ((list? (setFirst set))
            (if (element? (setFirst set) (setRest set))
             #f
             (set? (setFirst set))))
          (else (if (element? (setFirst set) (setRest set))
                #f
                (set? (setRest set))
                )
            )
        )
     )
 )

#tこれは、リストとその「サブリスト」に重複がないかどうかを返します。また、正常に機能する重複のあるリストから真のセットを作成する手順もあります。

4

4 に答える 4

2

正しい方向に導くためのいくつかの指針。

キーの比較に を使用しないことelement?を除いて、手順はほとんど正しいです。equal?same?same?

したがって、演習全体の正確さが の実装に依存することは想像に難くありませんsame?。そしてそれは、選択されたセット表現に依存します。すばらしい本 SICP には集合の表現に関する章全体があります (集合をリストとして表現することを含む)。

セットのプリミティブ プロシージャを実装したら、2 つのセットが等しいかどうかを確認するのは簡単です。実装はあなたに任せsetSizeますsetUnion。

(= (setSize a) (setSize b) (setSize (setUnion a b)))

または、@sds の回答で指摘されているように、2 つのセットが互いにサブセットである場合、それらが同じであるかどうかを判断できます。subset?手順は自分で実装する必要があります。

(and (subset? a b) (subset? b a))
于 2013-10-06T18:48:54.917 に答える
1

Racket プログラマーへの注意: できれば車輪の再発明は避けてください。racket/set適切な場合は、適切なセットの実装を提供する標準ライブラリの を使用してください。

于 2013-10-08T18:54:30.767 に答える
1

あなたの問題は、 のequal?セット要素を比較するために使用しているようですelement?。

element-equal?セット要素はアトムではなくリストである可能性があることを考慮して独自に作成し、代わりに使用する必要がありequal?ます。

-についてsame?は、次のように実装するのが最も簡単だと思います。

(define same? 
  (lambda (a b) 
    (and (subset? a b)
         (subset? b a))))

と

(define subset? 
  (lambda (a b)
    (or (isEmpty a)
        (and (element? (first a) b) 
             (subset? (rest a) b)))))
于 2013-10-06T18:47:49.243 に答える
0

私の研究室は実際に順調に進んでいます。コメントを寄せてくれたすべての人に感謝し、同じような実装に苦労している他の人たちにいくつかのことを言及したいと思います.

私の観点からの指針: -抽象的に考えてください。集合論の簡単な紹介を読んでください。セット、サブセット、空のセット、共用体などの定義を知るには十分です。

-すべての手順を紙に書き留め、どの手順が他にどの手順を必要とするかを考えます。

――同じ書き方を考えたときは？たとえば、すでに機能しているプロシージャ サブセットがあるとします。実際のところ、機能する手順はすでにたくさんあります (まだ持っていなくても =)) 心配しないで、同じ手順を試してみてください。できるだけきれいに作る必要があります。すべての手順について、このように続けます。

-プロシージャ間で物事をやり取りするだけで問題が発生し、プログラムが無限ループに陥る可能性があります。最初から注意して、いつこの問題が発生するかを認識していれば、それに遭遇するべきではありません。ただし、場合によっては、いくつかの手順を再考する必要があります。たぶん、彼らは同じことを達成するために他の手順を使用できますか?

また、いくつかの手順を共有して、あなたの考えを確認します. お気軽に解体してください。これまでのところ機能しています =) ..とにかく今週の金曜日が期限です。ps。私の proc makeSet は、基本的にそのように聞こえます。すべての「レベル」で重複する要素をすべて削除します。

;;; predicate that returns #t if a list is a set and #f otherwise
(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
      ((not (list? set)) #f)
      ((equal? (makeSet set) set) #t)
      (else #f))
  )
)

;;; diff returns the difference between set1 and set2
(define diff
  (lambda (set1 set2)
    (cond ((null? set1) '())
       ((null? set2) set1)
       ((not (member? (car set1) set2))
        (cons (car set1) (diff (cdr set1) set2)))
       (else (diff (cdr set1) set2)))
  )
)

ああ、すべての car、cdr、cons を「抽象化された」equals setFirst などに変更していません。また、diff がその戻り値の「makeSet-version」を返すようにして、常にセットが戻り値として取得されるようにすることもできます。

みんなありがとう！/レム

于 2013-10-16T18:06:04.163 に答える