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

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

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

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

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
;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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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 '()))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,704 Записей в блоге: 14
	28.09.2016, 10:12
	Kris123, приведи пример исходных данных и того, что должно получиться. 0

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

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,704 Записей в блоге: 14
	29.09.2016, 10:15
	Вот есть список (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 [ТС]
	(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 [ТС]
	Спасибо большое! Я, конечно, извиняюсь, но можно это как-то сделать в одной функции с хвостовой рекурсией?! 0