在 Scheme 中创建一个集合的分区

Question

我对整体计划还很陌生，我在为学校布置作业时遇到了一些问题。所以请不要给出完整的答案，只是寻找一点见解或朝着正确的方向推动，这样我就可以自己解决这个问题。

问题如下：给定一个数字列表，确定是否可以从这些数字的等价总和和项目数中得出两个子集。因此，例如，如果给定的集合是 (1 1)，那么我的程序应该 return #t，否则是 #f.

这是我到目前为止所写的内容（即使目前没有输出）

(define l (list '(7 5)))

(define s1 0)
(define s2 0)
(define l1 0)
(define l2 0)

(define two-subsets
  (lambda (l s1 s2 l1 l2)
    (if (null? l)
          (if (and (= s1 s2) (= l1 l2))
              (#t))
          (if (not (and (= s1 s2) (= l1 l2)))
              (#f)))
    (or ((two-subsets(cdr l) (+ s1 1) s2 (+ l1 1) l2) (two-subsets(cdr l) s1 (+s2 1) l1 (+ l2 1))))))

我的函数应该递归地将项目添加到子集 1 (s1, l1) 或子集 2 (s2, l2) 直到它到达基本情况，在该基本情况下它确定子集是否具有相等的大小和总和。我觉得我的逻辑在那里/接近，但我不确定如何在方案中正确实施这些想法。

EDIT 我要补充一点，作为作业的一部分，我必须使用递归。我希望 DrRacket 提供更多调试信息，因为当我点击运行时，它没有给出任何错误，但也没有输出。

Answer 1

对于第一遍，您可能希望避免尝试将 "subset" 逻辑耦合到 "do two subsets add to the same value" 逻辑。小程序比大程序好写

但这可能是一个复杂的问题。

一种解决方法叫做 "wishful thinking." 我们将从头开始：解决这个问题的最后步骤是什么？比较相同长度的两个子集的总和是否为相同的值。那么，让我们解决这个问题。然后我们只对相同长度的所有子集执行此操作。但是现在我们需要知道：相同长度的子集的所有组是什么？如果我们解决了那个问题，那么到最后的一切都结束了。所以让我们解决这个问题。然后我们将其应用于所有子集的集合。但是现在我们需要知道：我们如何得到所有子集的集合？如果我们解决了那个问题，那么到最后的一切都结束了。我们将把它应用到我们的集合中。但是现在我们需要知道：我们的集合是什么？ -哦！这就是问题本身。大功告成！

其实在细节上还是有点棘手，但是通过上面的阐述，我想你可以看出这条链的逻辑：

(find-first-equal-sum ; we can stop as soon as #t, if there is #t
  (make-pairs ; problem only wants us to consider pairs
    (sum-subsets ;we need sums eventually
       (at-least-two-in-a-group ; can't make pairs without at least two in a group
        (group-by-length ; only care about matching subsets of the same length
         (at-least-length-2 ; singles can't match because each element of a set is unique
          (subsets problem-set)))))))

注意：我确实编写了这个程序并在发布之前对其进行了测试。上面"outline"是直接从DrRacket复制过来的

Answer 2

问题

您的代码中存在一些问题。

第一个

这将创建一个列表的列表：

(list '(7 5))  ; => ((7 5))

其中的一个 cdr 始终是一个空列表。

(cdr (list '(7 5)))  ; => ()

单个列表是这样创建的：

(define l (list 7 5))

或者这样：

(define l '(7 5))

第二个

您在Scheme中使用括号进行应用。这个：

(#t)

表示"execute the function #t"。但是 #t 不是一个函数，它是一个布尔值。并且布尔值无法执行。

你可以直接return一个布尔值

#t

或者你可以return一个函数return计算值

(lambda () #t)

但是你不能执行true。

第三

or 中存在同样的问题。以下代码：

(or ((two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
     (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1))))

表示：two-subsets必须return一个函数。由第一个 two-subsets 调用编辑的函数 return 与由第二个 two-subsets 调用编辑的函数 return 一起执行。并将单个结果值传递给 or。这可能不是你想要的。

如果你想 or 两次调用 two-subsets 的两个 return 值，你必须删除两个括号。

(or (two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
    (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1)))

提示

定义一个符合您的结束条件的函数。该函数接受两个列表参数并检查它们是否具有相同的大小 (length) 和总和（您可以使用 apply 将列表传递给 +）。 Spoiler
编写一个遍历所有可能子集的函数。并用每个组合调用你的匹配函数。在 Scheme 中迭代是通过递归完成的。要么定义一个调用自身的函数，要么使用命名的 let.

在 Scheme 中创建一个集合的分区

Creating a partition of a set in Scheme

scheme

racket

partition-problem

问题

第一个

第二个

第三

提示