计划中所有大小的n个子列表

Question

我是Scheme语言的新手，我试图建立一个方法，该方法得到一个列表和一个数字'n'作为参数，并返回所有大小为n的子列表。

例如，如果该方法收到 '(a b c d) 和 2，它将返回 '('(a b) '(b c) '(c d)).

该方法必须是递归的。

我已经设法得到了第一个大小的 n 列表，但从那里卡住了。

先谢谢你。

(define sub-lists
  (lambda (lst n)
    (if (zero?  n)
        '()
        (cons (car los) (sub-lists (cdr lst) (- n 1))))))

Answer 1

这里有一个方法，你可以用以下方法来做 append 和 map -

(define (choose n l)
  (cond ((zero? n)
         (list null))
        ((null? l)
         null)
        (else
         (append (map (lambda (comb)
                        (cons (car l) comb))
                      (choose (- n 1)
                              (cdr l)))
                 (choose n
                         (cdr l))))))

它提供了一个有效的结果，对任何自然 n，包括零-

(choose 3 '(a b c))
;; '((a b c))

(choose 2 '(a b c))
;; '((a b) (a c) (b c))

(choose 1 '(a b c))
;; '((a) (b) (c))

(choose 0 '(a b c))
;; '(())

它提供了一个有效的结果，当 n 超出 l 也

(choose 4 '(a b c))
;; '()

可能的实施办法 append 和 map -

(define (append a b)
  (if (null? a)
      b
      (cons (car a)
            (append (cdr a)
                    b))))

(define (map f l)
  (if (null? l)
      null
      (cons (f (car l))
            (map f
                 (cdr l)))))

---

如果你希望元素重复，你只需要改变一个表达式----。

(define (choose n l)
  (cond ((zero? n)
         (list null))
        ((null? l)
         null)
        (else
         (append (map (lambda (comb)
                        (cons (car l) comb))
                      (choose (- n 1)
                              l)) ;; change (cdr l) to l
                 (choose n
                         (cdr l))))))

现在，这些组合包含了重复的元素 -

(choose 3 '(a b c))
;; '((a a a) (a a b) (a a c) (a b b) (a b c) (a c c) (b b b) (b b c) (b c c) (c c c))

(choose 2 '(a b c))
;; '((a a) (a b) (a c) (b b) (b c) (c c))

(choose 1 '(a b c))
;; '((a) (b) (c))

(choose 0 '(a b c))
;; '(())

请注意在以下情况下的显著差异 n 超过 l -

(choose 4 '(a b c))
;; '((a a a a)
;;   (a a a b)
;;   (a a a c)
;;   (a a b b)
;;   (a a b c)
;;   (a a c c)
;;   (a b b b)
;;   (a b b c)
;;   (a b c c)
;;   (a c c c)
;;   (b b b b)
;;   (b b b c)
;;   (b b c c)
;;   (b c c c)
;;   (c c c c))