0

我需要编写一个函数来生成给定列表的所有可能子集。我相信我应该使用 map,但我正在努力想出正确的迭代语法。我必须在任何地方插入 lambda 语句吗?

的所有可能子集(list 1 2 3)应该是:

(list (list) 
      (list 1) (list 2) (list 3) 
      (list 1 2) (list 2 3) (list 1 3) 
      (list 1 2 3)))
4

2 回答 2

0

考虑通过包含或不包含每个项目来生成一个幂集。基本情况是如果您没有项目,在这种情况下,幂集是具有空集的集。伪代码将是:

Powerset([]) = [[]]
Powerset(first:rest) = 
    let subPowersets = Powerset(rest) in
        [subPowerset for subPowerset in subPowersets] ++
        [first:subPowerset for subPowerset in subPowersets]
于 2013-10-17T00:51:02.153 回答
0

你也可以试试:

(define power-set 
 (lambda (set)
   (if (empty? set) '()
        (remove-duplicates (append* (power-set (car set))
                                          (map (lambda (x) (cons (car A) x)) (power-set (cdr A))))))))

虽然我将此代码与其他函数一起使用,例如 (set-union) 而不是 (remove-duplicates (append*...)) 此外,我使用另一个函数根据它们的基数对它们进行排序。

您可以通过阅读其数学定义来构建这些简单的程序。您可以通过阅读文档来改进它们(一些数学定义会导致“错误”递归,您可以尝试使用tail-recursion

于 2013-10-17T17:40:26.367 回答