Вернуть список позиций вхождения list2 в list1 и глубину нахождения list2 в list1

@Kris123 · Регистрация: 14.09.2014

Author24 — интернет-сервис помощи студентам

Здравствуйте! Делаю не на лиспе, но язык такой же практически, немного названия функций другие.
Задание: написать функцию, возвращающую список позиций вхождения list2 в list1 и глубину нахождения list2 в list1.
Сделала для возвращения глубины. Подскажите как доделать до нужного результата?

Lisp

;count - счетчик списков на текущей глубине
;newL - список элементов на следующей глубине
 
#lang racket
(define (fun L A1)
  (define (fun-iter L newL tekGlubina count)
    (if (null? L)
        (if (= count 0) tekGlubina
            (fun-iter newL '() (+ tekGlubina 1) 0))
        (let ((fstL (car L)))
          (if (list? fstL)
              (fun-iter (cdr L) (append fstL newL) tekGlubina (+ count 1))
              (fun-iter (cdr L) newL tekGlubina count)))))
  (fun-iter L '() 1 0))
 
(fun '(1 ((1)) 5 6) 1)

@Catstail · 28.09.2016, 10:12

Kris123, приведи пример исходных данных и того, что должно получиться.

@Kris123 · 28.09.2016, 19:32 **[ТС]**

Чуть-чуть изменилась формулировка: Функция должна возвращать список, содержащий информацию о количестве подсписков на каждом уровне вложенности ((<уровень> <количество подсписков>)...)

@Catstail · 29.09.2016, 10:15

Вот есть список (a b (c d) ((e f ((g h) (i j) k)))). Что должна вернуть функция?

@Kris123 · 01.10.2016, 12:21 **[ТС]**

(1 2) (2 1) (3 1) (4 2)
1-й уровень: (c d) ((e f ( (g h) (i j) k)))
2-й: (e f ( (g h) (i j) k))
3-й: ( (g h) (i j) k)
4-й: (g h) (i j)

@_sg · 01.10.2016, 18:43

Lisp

(defun dive-count (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) 0)
         ((= n 0) (count-if #'listp w))
         ((atom a) (dive-count n d))
         ((+ (dive-count (1- n) a) (dive-count n d)))))
 
(defun max-depth (w)
  (if (atom w)
      -1
      (max (1+ (max-depth (car w)))
           (max-depth (cdr w)))))
 
(defun level-number-of-lists (w &aux (n (1- (max-depth w))))
  (loop for a from 0 to n
        collect (list a (dive-count a w))))
 
> (level-number-of-lists '(a b (c d) ((e f ((g h) (i j) k)))))
((0 2) (1 1) (2 1) (3 2))

@Kris123 · 01.10.2016, 18:47 **[ТС]**

Спасибо большое! Я, конечно, извиняюсь, но можно это как-то сделать в одной функции с хвостовой рекурсией?!

@_sg · 01.10.2016, 19:22

вариант "простая рекурсия":

Lisp

(defun dive-count (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) 0)
         ((= n 0) (count-if #'listp w))
         ((atom a) (dive-count n d))
         ((+ (dive-count (1- n) a) (dive-count n d)))))
 
(defun max-depth (w)
  (if (atom w)
      -1
      (max (1+ (max-depth (car w)))
           (max-depth (cdr w)))))
 
(defun level-number-of-lists (w &optional (n (max-depth w)) (m 0))
  (when (< m n) (cons (list m (dive-count m w)) 
              (level-number-of-lists w n (1+ m)))))
 
> (level-number-of-lists '(a b (c d) ((e f ((g h) (i j) k)))))
((0 2) (1 1) (2 1) (3 2))

Добавлено через 40 секунд
вариант "хвостовая рекурсия"

Lisp

(defun dive-count (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) 0)
         ((= n 0) (count-if #'listp w))
         ((atom a) (dive-count n d))
         ((+ (dive-count (1- n) a) (dive-count n d)))))
 
(defun max-depth (w)
  (if (atom w)
      -1
      (max (1+ (max-depth (car w)))
           (max-depth (cdr w)))))
 
(defun level-number-of-lists (w &optional ac (n (max-depth w)) (m 0))
  (if (< m n)
      (level-number-of-lists w
                 (cons (list m (dive-count m w))
                   ac)
                 n
                 (1+ m))
      (reverse ac)))
 
> (level-number-of-lists '(a b (c d) ((e f ((g h) (i j) k)))))
((0 2) (1 1) (2 1) (3 2))

Добавлено через 15 минут
вариант "одна функция":

Lisp

(defun level (w
          &optional
          ac
          (n (labels ((max-depth (v)
                (if (atom v)
                -1
                (max (1+ (max-depth (car v)))
                     (max-depth (cdr v))))))
           (max-depth w)))
          (m 0))
  (if (< m n)
      (level w
         (cons (list m
             (labels ((dive-count (n
                           v
                           &aux
                           (a (car v))
                           (d (cdr v)))
                    (cond ((null v) 0)
                      ((= n 0) (count-if #'listp v))
                      ((atom a) (dive-count n d))
                      ((+ (dive-count (1- n) a)
                          (dive-count n d))))))
               (dive-count m w)))
           ac)
         n
         (1+ m))
      (reverse ac)))
 
> (level '(a b (c d) ((e f ((g h) (i j) k)))))
((0 2) (1 1) (2 1) (3 2))

@Catstail · 02.10.2016, 09:37

Еще решение:

Lisp

(defun task (lst &optional (lv 1))
  (cond ((null lst) 0)
        ((= lv 1) (count-if #'listp lst))
        (t (apply '+ (mapcar #'(lambda (x) (if (atom x) 0 (task x (- lv 1)))) lst)))))
 
==> TASK
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 2)
 
==> 1
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 1)
 
==> 2
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 3)
 
==> 1
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 4)
 
==> 2
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 5)
 
==> 0

Или даже так (без явной терминальной ветви):

Lisp

(defun task (lst &optional (lv 1))
  (apply '+ (mapcar #'(lambda (x) 
                        (if (= lv 1)
                            (if (atom x) 0 1)
                            (if (atom x) 0 (task x (- lv 1))))) lst)))
 
==> TASK
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 5)
 
==> 0
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 4)
 
==> 2
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 2)
 
==> 1
 
(task '(a b (c d) ((e f ((g h) (i j) k)))) 1)
 
==> 2

Добавлено через 10 минут
Kris123, имей в виду, что приведены решения для Лиспа, а не для Схемы.

@Kris123 · 07.10.2016, 18:04 **[ТС]**

Вот программа на Scheme. Работает, при (a b (c d) ((e f ((g h) (i j) k))))
ответ '((0 2) (1 1) (2 1) (3 2)), это правильно.
Но при (a b (c d) ((e f ((g h) (i () j) k)))) - ответ такой же, т.е. не появляется (4 1), если просто пустой список. Помогите, пожалуйста, исправить.

Lisp

#lang racket
(define (func L)
  (define (inter L newL lvl count result)
    (cond
      [(null? L) (if (null? newL) (reverse result)
                     (inter newL '()
                            (+ lvl 1)
                            0
                            (cons (list lvl count)
                                  result)))]
      [(list? (car L)) (inter (cdr L) (append (car L) newL)
                              lvl
                              (+ count 1)
                              result)]
      [else (inter (cdr L) newL lvl count result)]))
  (inter L '() 0 0 '()))
 
(func '(a b (c d) ((e f ((g h) (i () j) k)))))
(func '(a b (c d) (e)))
(func '(a b ((c d) (e))))

@rdt · 08.10.2016, 00:42

Kris123, мне такой вариант пришёл в голову:

Lisp

#lang racket
 
(define (func L)
  (define (inter L newL lvl count result)
    (cond
      [(null? L) (if (null? newL) (reverse result)
                                  (inter newL
                                         '()
                                         (+ lvl 1)
                                         0
                                         (cons (list lvl count)
                                         result)))]
      [(list? (car L)) (inter (cdr L)
                              (append (cons 1 (car L)) newL)
                              lvl
                              (+ count 1)
                              result)]
      [else (inter (cdr L) newL lvl count result)]))
  (inter L '() 0 0 '()))

@Catstail Модератор 36587 / 20317 / 4218 Регистрация: 12.02.2012 Сообщений: 33,614 Записей в блоге: 13
	28.09.2016, 10:12	2
	Kris123, приведи пример исходных данных и того, что должно получиться. 0

@Kris123 2 / 2 / 0 Регистрация: 14.09.2014 Сообщений: 82
	28.09.2016, 19:32 [ТС]	3
	Чуть-чуть изменилась формулировка: Функция должна возвращать список, содержащий информацию о количестве подсписков на каждом уровне вложенности ((<уровень> <количество подсписков>)...) 0

@Catstail Модератор 36587 / 20317 / 4218 Регистрация: 12.02.2012 Сообщений: 33,614 Записей в блоге: 13
	29.09.2016, 10:15	4
	Вот есть список (a b (c d) ((e f ((g h) (i j) k)))). Что должна вернуть функция? 0

@Kris123 2 / 2 / 0 Регистрация: 14.09.2014 Сообщений: 82
	01.10.2016, 12:21 [ТС]	5
	(1 2) (2 1) (3 1) (4 2) 1-й уровень: (c d) ((e f ( (g h) (i j) k))) 2-й: (e f ( (g h) (i j) k)) 3-й: ( (g h) (i j) k) 4-й: (g h) (i j) 0

@Kris123 2 / 2 / 0 Регистрация: 14.09.2014 Сообщений: 82
	01.10.2016, 18:47 [ТС]	7
	Спасибо большое! Я, конечно, извиняюсь, но можно это как-то сделать в одной функции с хвостовой рекурсией?! 0

	08.10.2016, 00:42