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。

于 2015-11-30T00:55:43.350 回答