如何使用 powerset 函数求子集之和

Question

对于这个问题，我有一个称为 powerset 函数的函数

(define (powerset set)
  (if (null? set)
      '(())
      (let ((rest (powerset (cdr set))))
        (append (map (lambda (element) (cons (car set) element))
                     rest)
                rest))))

如果从 powerset 函数生成的子集的总和等于作为参数传入的总和，我想将该函数用于 return true。我认为我的想法是正确的，但我不确定如何实施。我知道这个函数生成的列表应该一次传递给另一个函数 1 子集。在该函数中，我想将子集中的这些值加在一起，看看它们是否等于总和。到此为止，但我知道这是错误的。

(define (group list sum)
 (cond((null? list) #f)
      ((equal? (apply + (powerset list)) sum)#t)
      (else (group((powerset list))sum)) ))

所以我需要一个调用 powerset 一次并将列表一次传递给另一个函数的函数，该函数将子集的总和与作为总和传递的值进行比较。

例如，如果我调用：

(group '(1 2 4 5) 9)

我想要 return #t 因为子集 (4, 5) 求和等于 9。如果您知道如何使用 powerset 并且可以展示解决此问题的示例，我们将不胜感激.

Answer 1

一种方法是在您的子集列表上映射求和函数，这将为您提供一个列表，其元素对应于每个子集的总和。然后您可以检查此总和列表中的任何元素是否等于提供的目标总和。

一种方法是这样的：首先我们需要一个函数来对列表求和。我们可以为此使用折叠：

(define (sum set)
    (fold-right + 0 set))

现在，我们定义一个函数，如果给定元素包含在提供的列表中，则该函数将 return 为真，否则为假：

(define (contains n set)
    (if (null? set)
        #f
        (if (= (car set) n)
            #t
            (contains n (cdr set)))))

（我不是 Scheme 方面的专家，所以我不确定这是否是内置的）。

有了这个定义，我们就可以编写你想要的函数了：

(define (group set n)
    (contains n (map sum (powerset set))))

你可以测试你的例子 (group '(1 2 4 5) 9) 给我们 #t.

如何使用 powerset 函数求子集之和

How to use powerset function in finding the sum of subsets

scheme

racket