все размеры n подсписков в схеме - PullRequest
Новая
       41

все размеры n подсписков в схеме

0 голосов
/ 16 марта 2019

Я новичок в языке схем и пытаюсь создать метод, который получает в качестве параметров список и число 'n' и возвращает все подсписки размером n.например, если метод получает '(abcd) и 2, он возвращает' ('(ab)' (bc) '(cd)), метод должен быть рекурсивным.Мне удалось получить первый размер n списка, но застрял оттуда.заранее спасибо. 

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

1 Ответ

0 голосов
/ 16 марта 2019

Вот способ, которым вы можете сделать это, используя 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))
...