如何定义接受一个集合(不同元素的列表)并生成该集合的所有子集的列表的Scheme过程？ [英] How do I define a Scheme procedure that takes a set (a list of distinct elements) and generates a list of all subsets of the set?

问题描述

首先，我想澄清一下，我知道有一些与我要问的问题类似的问题，但是我有一个非常具体的输出案例，我正在尝试复制该案例。

我正在尝试创建一个Scheme过程，该过程允许我获取一个集合并生成一个列表，该列表显示该集合的所有可能子集。

例如，如果我调用：(subsets '(a b c ))，我应该得到：'((a b c) (b c) (a c) (c) (a b) (b) (a) ())(具体按该顺序)

以下是我到目前为止的情况：

(define (subsets givenList)
  (if (null? givenList)
      (list null)
      (let ((rest (subsets (cdr givenList))))
        (append rest (map (lambda (x)
                            (cons (car givenList) x))
                          rest)))))

我的输出为：(() (c) (b) (b c) (a) (a c) (a b) (a b c))，但这不是我要查找的特定输出。 有什么建议吗？

推荐答案

要按所需顺序获取'(a b c)的所有子集的列表，请执行以下操作：

• 首先，作为归纳假设，假设您有一个R列表，其中'(b c)的所有子集按所需顺序排列，即R = '((b c) (c) (b) ())。
• 然后，将R的每个子列表映射到以a元素开始的另一个子列表，即可创建S = '((a b c) (a c) (a b) (a))列表。
• 最后，您可以交织S和R的元素，从S的第一个元素开始，得到最终的列表'((a b c) (b c) (a c) (c) (a b) (b) (a) ())。

(define (subsets L)
  (if (null? L)
      (list null)
      (let* [(R (subsets (cdr L)))
             (S (map (lambda (x) (cons (car L) x)) R))]
        (interleave S R))))

(define (interleave A B)
  (cond [(null? A) B]
        [(null? B) A]
        [else (cons (car A) (cons (car B) (interleave (cdr A) (cdr B))))]))

示例：

> (subsets '(a b c))
'((a b c) (b c) (a c) (c) (a b) (b) (a) ())

这篇关于如何定义接受一个集合(不同元素的列表)并生成该集合的所有子集的列表的Scheme过程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！