在方案中实施电源集 [英] Implementing powerset in scheme

问题描述

我试图以两种方式在Scheme中实现powerset函数.一种方法是使用尾递归，而我这样做是这样的:

I am trying to implement a powerset function in Scheme in two ways. One way is using tail recursion, and I did it like this:

(define (powerset list)
 (if (null? list) '(())                                    ;; if list is empty, its powerset is a list containing the empty list
  (let ((rest (powerset (cdr list))))                   ;; define "rest" as the result of the recursion over the rest of list
    (append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest) 
            rest))))                                    ;; and append it to rest itself (as we can either use the current element (car list), or not

哪个工作正常.

另一种方法是使用 folder ，这是我面临的一些问题.我当前的实现如下:

Another way is using foldr, and this is where I face some issues. My current implementation is as follows:

(define (powerset-fr list)
 (foldr (lambda (element result)        ;; This procedure gets an element (and a result);
       (if (null? result) ;; if starting with the empty list, there is nothing to "fold over".
           (cons '() (cons element result))
           (foldr (lambda (inner-element inner-result)
                    (append (cons element result) inner-result))
                  '(())
                  result)))
     '()                             ;; The result is initialized to the empty list,
     list))                         ;; and the procedure is being applied for every element in the first list (list1)

结果不好.

我将尽力解释目前为止我是如何解决这个问题的:

I'll try to explain shortly how did I approach this problem so far:

folder在给定集中的每个元素上运行.对于每个这样的元素，我应该在powerset中添加一些新元素.这些应该是哪些元素?powerset中每个现有元素的一个新元素，其中将列表中的当前元素追加到powerset中的现有元素.

foldr runs over every element in the given set. For each such element, I should add some new elements to the powerset. Which elements should these be? One new element for each existing element in the powerset, where is append the current element in list to the existing element in powerset.

这就是为什么我认为我应该以嵌套方式使用文件夹两次-遍历给定列表中的所有项目，对于每个项目，我都使用文件夹遍历结果"中的所有项目(当前电源设置).

This is why I thought I should use foldr twice in a nested way - one to go over all items in given list, and for each item I use foldr to go over all items in "result" (current powerset).

我遇到了一个空列表的问题(没有在powerset中添加任何内容)，因此添加了"if"部分(而不仅仅是文件夹)，但是它也不能很好地工作.

I faced the problem of the empty list (nothing is being added to the powerset), and thus added the "if" section (and not just foldr), but it doesn't work very well either.

我认为就是这样.我感觉很亲密，但仍然很有挑战性，因此将竭诚欢迎您的帮助.谢谢！

I think that's it. I feel close but it is still very challenging, so every help will be welcomed. Thanks!

推荐答案

解决方案更简单，无需使用双 folder ，请尝试以下操作:

The solution is simpler, there's no need to use a double foldr, try this:

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append (map (lambda (x) (cons e x)) 
                        acc) 
                   acc))
         '(())
         lst))

如果您的解释器定义了

If your interpreter defines append-map or something equivalent, then the solution is a bit shorter - the results will be in a different order, but it doesn't matter:

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append-map (lambda (x) (list x (cons e x)))
                       acc))
         '(())
         lst))

无论哪种方式，它都能按预期工作:

Either way, it works as expected:

(powerset-fr '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

这篇关于在方案中实施电源集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！