lisp - R5RS 中的数字分区

Question

在一次实习面试中，我被要求做一个 R5RS 程序，该程序创建一个函数，比如说两个子集。如果列表 L 包含两个元素总和和元素数量相等的子集，则该函数必须返回 #t，否则返回 #f。它的入口是列表L(只有正数)和一些参数(我认为有用的。参数的数量没有条件)一开始都等于0。

我还记得的要求如下: - 不要定义其他函数并在“两子集”函数内调用它们。 - 它只能使用以下结构:null?、cond、car、cdr、else、+、=、not、and、#t、#f、两个子集(本身用于递归调用)、参数名称、例如列表、总和……等、数字常量和括号。

有一些关于我们应该得到的结果的示例，比方说:

(two-subsets '(7 7) 0 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(7 7 1) 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(5 3 2 4) 0 0) returns #t. The two subsets are {2, 5} and {3, 4}. 
(two-subsets '(1 2 3 6 9) 0 0) returns #f. 

我首先写了签名，在我看来它应该是这样的:

(define two-subsets (lambda (L m n ... other parameters)
                    (cond

问题确实很复杂，复杂度明显超过了O(n)，我在https://en.wikipedia.org/wiki/Partition_problem上读到过。 .

我尝试在编码之前先定义算法。我考虑将列表 L 的总和作为参数，因此在我的条件下，我只会迭代总和 <= sum(L)/2 的组合。通过这样做，我可以稍微降低问题的复杂性，但我仍然不知道如何做到这一点。

这看起来是一个有趣的问题，我真的想了解更多。

Answer 1

这是一个不依赖于全部正数的版本。我有理由相信，通过了解它们，您可以做得更好。

请注意，这假设:

• 分区不需要详尽；
• 但集合不能为空。

我很想看到一个依赖于列表元素+ve的版本!

(define (two-subsets? l sl sld ssd)
  ;; l is the list we want to partition
  ;; sl is how many elements we have eaten from it so far
  ;; sld is the length difference in the partitions
  ;; ssd is the sum difference in the partitions
  (cond [(and (not (= sl 0))
              (= sld 0)
              (= ssd 0))
         ;; we have eaten some elements, the differences are zero
         ;; we are done.
         #t]
        [(null? l)
         ;; out of l, failed
         #f]
        ;; this is where I am sure we could be clever about the set containing
        ;; only positive numbers, but I am too lazy to think

        [(two-subsets? (cdr l)
                       (+ sl 1)
                       (+ sld 1)
                       (+ ssd (car l)))
         ;; the left-hand set worked
         #t]
        [(two-subsets? (cdr l)
                       (+ sl 1)
                       (- sld 1)
                       (- ssd (car l)))
         ;; the right-hand set worked
         #t]
        [else
         ;; finally drop the first element of l and try the others
         (two-subsets? (cdr l) sl sld ssd)]))