Как вычислить количество раз шаблон в одном списке появляется в другом списке в схеме

Question

Я застрял в программе Scheme примерно на 5 часов.Программа, над которой я работаю, должна взять в качестве входных данных два списка, а затем вычислить, сколько раз шаблон из первого списка появляется во втором списке.

Например:> (patt '(b c) '(a b c d e b c)) ==> answer = 2

(patt '(abc)' (abcabcdeabccc)) ==> answer = 3

(patt '((ab) c)' (ab (ab) cdebc)) ==> answer = 1

Ниже приведен код, который у меня есть до сих пор.

(define (patt lis1 lis2)
  (cond
    ((null? lis1) 0)
    ((null? lis2) 0)
    [(and (> (length lis1) 1) (eq? (car lis1) (car lis2))) (patt (cdr lis1) (cdr lis2))]
    ((eq? (car lis1) (car lis2)) (+ 1 (patt lis1 (cdr lis2))))
    (else (patt lis1 (cdr lis2)))
    ))

Может кто-нибудь, пожалуйста, помогите мне решить эту проблему.Спасибо!

Answer 1

После того, как я уделил этой проблеме домашнее задание немного времени для маринования, я не вижу вреда в размещении дополнительных ответов -

(define (count pat xs)
  (cond ((empty? xs)
         0)
        ((match pat xs)
         (+ 1 (count pat (cdr xs))))
        (else
         (count pat (cdr xs)))))

(define (match pat xs)
  (cond ((empty? pat)
         #t)
        ((empty? xs)
         #f)
        ((and (list? pat)
              (list? xs))
         (and (match (car pat) (car xs))
              (match (cdr pat) (cdr xs))))
        (else
         (eq? pat xs))))

(count '(a b c) '(a b c a b c d e a b c c c)) ;; 3

(count '((a b) c) '(a b (a b) c d e b c)) ;; 1

(count '(a a) '(a a a a)) ;; 3

Answer 2

Вам нужно разделить задачу на части:

(define (prefix? needle haystack)
  ...)

(prefix? '() '(a b c))        ; ==> #t
(prefix? '(a) '(a b c))       ; ==> #t
(prefix? '(a b c) '(a b c))   ; ==> #t
(prefix? '(a b c d) '(a b c)) ; ==> #f
(prefix? '(b) '(a b c))       ; ==> #t

(define (count-occurences needle haystack)
  ...)

Таким образом, вы можете представить себе поиск шаблона (count-occurences '(a a) '(a a a a)).Когда он найден по первому элементу, вам нужно снова поискать следующий.Таким образом, чтобы результат был 3 для (a a a a), поскольку совпадения перекрываются.Каждый подсписок, кроме случаев, когда это пустой список, включает использование prefix?

Удачи!

Answer 3

(define (patt list1 list2)
  (let ([patt_length (length list1)])
    (let loop ([loop_list list2]
               [sum 0])
      (if (>= (length loop_list) patt_length)
          (if (equal? list1 (take loop_list patt_length))
              (loop (cdr loop_list) (add1 sum))
              (loop (cdr loop_list) sum))
          sum))))

Answer 4

Рассмотрим подзадачу тестирования, если список начинается с другого списка.

Затем сделайте это для каждого суффикса списка.Суммируйте количество совпадений.

Если вы хотите, чтобы совпадения не перекрывались, вы можете иметь совпадение префикса, вернуть суффикс списка, чтобы пропустить соответствующую часть.

Такжеиспользуйте equals? для структурного равенства, а не eq? для идентичности.