R5RS 中的数字分区

Question

我在一次实习面试中被要求做一个创建函数的 R5RS 程序，比方说两个子集。如果列表 L 包含两个元素总和相等且元素数量相等的子集，则此函数必须 return #t，否则它 returns #f。它接受列表 L（只有正数）和一些参数（我认为有用。参数数量没有条件）在开始时都等于 0。

我还记得当时的要求是： - 不要定义其他函数并在 "two-subsets" 函数中调用它们。 - 它只能使用以下结构：null?, cond, car, cdr, else, + ,=, not, and, #t, #f, two-subsets (itself for recursive call), 参数名称,例如列表、求和、...等、数字常量和括号。

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

(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)]))

R5RS 中的数字分区

Number Partitioning in R5RS

lisp

racket

r5rs