scheme - 筛选总和列表

Question

我需要编写一个函数，它使用整数列表 lst 并生成一个列表，该列表仅包含 lst 的唯一元素（无特定顺序），这些元素是 lst 中任何两个其他元素的总和。

前任：

(sumfilt '(1 4 7 5 17 11)) => '(11 5)
(sumfilt '(5 4 7 5 9 1 10)) => '(5 9 10)

有人可以帮我吗？我也希望这可以使其尽可能高效

Answer 1

我会给你一些提示来解决这个问题。第一种天真的方法是预先计算输入列表的每个大小为 2 组合的总和列表，然后测试以查看输入列表的哪些元素属于总和列表。作为最后一步，删除重复项。

假设comb存在用于计算lst具有给定大小的列表的所有可能组合的过程m（查找它，或自己实现它！），这里有一个非常简短的问题答案，实现上面解释的朴素算法 - 这应该足够好对于具有 1000 个左右元素的列表：

(require srfi/26) ; I like to use `cut`, but `lambda` would serve just as well

(define (comb lst m)
  <???>) ; ToDo: generate all m-size combinations of lst

(define (sumfilt lst)
  (let ((sums (map (cut apply + <>) (comb lst 2))))
    (remove-duplicates (filter (cut member <> sums) lst))))

或者等效地，cute仅用于评估预先计算的总和列表一次：

(define (sumfilt lst)
  (remove-duplicates
   (filter (cute member <> (map (cut apply + <>) (comb lst 2))) lst)))

更有效的方法将涉及子集和问题的一些变化，通过动态规划解决。不过，这样的解决方案编写起来会更复杂。无论哪种方式，不要忘记测试你的答案：

(sumfilt '(1 4 7 5 17 11)) 
=> '(5 11)

(sumfilt '(5 4 7 5 9 1 10)) 
=> '(5 9 10)

Answer 2

由于您的问题被标记为Racket，我想建议一个使用 Racket 成语的解决方案：

正如 Oscar 所建议的那样， allsums创建所有总和的列表。它基本上是一个嵌套循环，处理所有必要的组合。为了不重复，我使用了一组在添加时会静默删除它们。稍后，该集合被转换为列表。

(define (allsums lst)
  (let* ([len (length lst)] [len-1 (sub1 len)])
    (set->list
     (for*/set ([i (in-range 0 len-1)]
                [j (in-range (add1 i) len)])
       (+ (list-ref lst i) (list-ref lst j))))))

sumfilt现在根据allsums生成的列表过滤您的列表。同样，一组用于删除重复项：

(define (sumfilt lst)
  (let ([as (allsums lst)])
    (set->list
     (for/set ([i lst] #:when (member i as))
       i))))

如

> (sumfilt '(1 4 7 5 17 11))
'(5 11)
> (sumfilt '(5 4 7 5 9 1 10))
'(5 9 10)

但是如果你需要一个纯 Scheme 解决方案，这个代码就可以了，只使用经典的形式和习语：

(define (allsums lst)
  (let loop1 ((lst lst) (res '()))
    (if (empty? lst)
        (reverse res)
        (let loop2 ((a (car lst)) (bs (cdr lst)) (res res))
          (if (empty? bs)
              (loop1 (cdr lst) res)
              (let ((s (+ a (car bs))))
                (loop2 
                 a 
                 (cdr bs) 
                 (if (member s res) res (cons s res)))))))))

(define (sumfilt lst)
  (let ((as (allsums lst)))
    (let loop ((lst lst) (res '()))
      (if (empty? lst)
          (reverse res)
          (let ((ca (car lst)))
            (loop 
             (cdr lst) 
             (if (and (member ca as) (not (member ca res)))
                 (cons ca res)
                 res)))))))

给予

> (sumfilt '(1 4 7 5 17 11))
'(5 11)
> (sumfilt '(5 4 7 5 9 1 10))
'(5 9 10)