3

这是一种递归算法，用于产生集合的所有子集。等效的 Python 代码是：

def subsets(s):
    if not s:
        yield ()
    else:
        for e in subsets(s[1:]):
            yield s[:1] + e
            yield e

for s in subsets((1,2,3)):
    print(s)

结果：

>>> 
(1, 2, 3)
(2, 3)
(1, 3)
(3,)
(1, 2)
(2,)
(1,)
()

这是我试过的球拍版本：

#lang racket
(require racket/generator)

(define (subsets x)
  (generator ()
   (let recur ([s x])
     (if (null? s) 
         (yield '())
         (for ([e (in-producer (recur (cdr s)))])
           (yield (cons (car s) e))
           (yield e))))))

(for/list ([j (in-producer (subsets '(1 2 3)))])
    (display j))

但它不起作用：

Welcome to DrRacket, version 6.0.1 [3m].
Language: racket; memory limit: 128 MB.
(). . result arity mismatch;
 expected number of values not received
  expected: 1
  received: 0
  values...:

Racket文档中似乎没有相关示例是否可能，如何？

4

2 回答 2

3

您总体上非常接近，但有一些小问题：

  • 您使subsets函数获取集合并正确返回生成器，但随后您无缘无故地决定将主体包装在recur循环中...您希望递归调用返回生成器（用作生产者），因此您只需要打电话 subsets。

  • 迭代生成器的正确方法是让它在完成后返回某个已知值，并将其用作停止值。比如最后加一个(void)，用它来停止。

  • 您不应该混合使用for/list-display第一个用于收集结果列表，第二个用于显示值。要么切换到for，要么只删除display以返回子集列表。

修复这些会给出工作代码：

#lang racket
(require racket/generator)

(define (subsets s)
  (generator ()
    (if (null? s)
      (yield '())
      (for ([e (in-producer (subsets (cdr s)) (void))])
        (yield (cons (car s) e))
        (yield e)))
    (void)))

(for ([j (in-producer (subsets '(1 2 3)) (void))])
  (displayln j))

两侧评论：

  • 关于 Oscar 的解决方案的一个小评论： usingin-generator可能有点令人困惑，因为它不是一种迭代生成器的方法，而是一种创建生成器并立即迭代它的方法。

  • JFYI，如果您关心效率（而不是使用生成器），这并不是一个真正的好方法。

于 2014-08-13T17:57:08.523 回答
2

我认为程序可以简化一点。以下等价于 Python 中的代码，注意我们如何使用in-generator：

(require racket/generator)

(define (subsets s)
  (if (null? s) 
      (yield '())
      (for ([e (in-generator (subsets (cdr s)))])
        (yield (cons (car s) e))
        (yield e))))

像这样称呼它：

(for ([e (in-generator (subsets '(1 2 3)))])
  (displayln e))

=> (1 2 3)
   (2 3)
   (1 3)
   (3)
   (1 2)
   (2)
   (1)
   ()
于 2014-08-13T16:28:24.437 回答