0

スキームサブセット再帰問題

累乗関数の場合:

(define (p l)

  (define (n next)
    (if (null? next)
        '()
        (cons (car next)
              (cons (cons (car l) (car next))
                    (n (cdr next))))))

  (if (null? l)
      '(())
      (n (p (cdr l)))))

R5RS のみを使用して、すべてのセットを要素数の昇順で印刷し、同じサイズをソート順に印刷したいと思います。例えば、

このようなリストを定義すると

(define list3 (list '1 '2 '3))

関数を呼び出し、

(p'(1 2 3))

私の出力は

(() (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))

しかし、私は次のように印刷したい:

(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

また、次の場合については、

(p'(1 2 3 4))

私の出力は次のとおりです。

(()
 (1)
 (2)
 (1 2)
 (3)
 (1 3)
 (2 3)
 (1 2 3)
 (4)
 (1 4)
 (2 4)
 (1 2 4)
 (3 4)
 (1 3 4)
 (2 3 4)
 (1 2 3 4))

でも私はしたい

(()
 (1)
 (2)
 (3)
 (4)
 (1 2)
 (1 3)
 (1 4)
 (2 3)
 (2 4)
 (3 4)
 (1 2 3)
 (1 2 4)
 (1 3 4)
 (2 3 4)
 (1 2 3 4))

正しい出力を行うにはどうすればよいですか?

4

1 に答える 1

1

簡単な代替手段があります: パワー セット プロシージャの現在の実装を使用し、必要に応じて出力を並べ替えます。

(define (compare s1 s2)
  (let ((cmp (- (length s1) (length s2))))
    (cond ((negative? cmp) #t)
          ((positive? cmp) #f)
          (else (less-than? s1 s2)))))

(define (less-than? s1 s2)
  (cond ((or (null? s1) (null? s2)) #f)
        ((< (car s1) (car s2))  #t)
        ((> (car s1) (car s2))  #f)
        (else (less-than? (cdr s1) (cdr s2)))))

しかし、ここに落とし穴があります -sort手順が必要ですが、それは R5RS の一部ではありません:

(sort (p '(1 2 3)) compare)
=> '(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

もちろん、要素を比較するための手順を受け取る独自の並べ替え手順を実装することはそれほど難しくありません。または、許可されている場合は、SRFI の 1 つなど、既存のライブラリからインポートできます。

于 2015-11-30T00:55:43.350 に答える