使用递归的列表子集

我需要编写一个函数来生成给定列表的所有可能的子集。我相信我应该使用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)))

来源

2013-10-17 user2888512

可能重复[Memory efficiency power set algorithm]（http://stackoverflow.com/questions/7371264/memory-efficient-power-set-algorithm），在链接的文章中有一个Scheme实现 –

谢谢。通过权力集算法问题的答案看真的很有帮助。 – user2888512

思考。基本情况是，如果你没有物品，在这种情况下，功率集是空集的集合。伪代码将是：

Powerset([]) = [[]] 
Powerset(first:rest) = 
    let subPowersets = Powerset(rest) in 
     [subPowerset for subPowerset in subPowersets] ++ 
     [first:subPowerset for subPowerset in subPowersets]

来源

2013-10-17 00:51:02 Claudiu

谢谢。我现在得到如何设置功能。 – user2888512

你还可以尝试：

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

虽然我使用此代码与其他功能，如（设置工会）代替（删除，复制（追加*。 ..））另外，我根据他们的基数用另一个函数对它们进行分类。

你可以通过阅读它的数学定义来构造这些简单的程序。你可以通过阅读文档来改进它们（一些数学定义导致'不好'递归，你可以尝试使用tail-recursion）

来源

2013-10-17 17:40:26

使用递归的列表子集

回答

相关问题