Сравнение списков

@Hrizofilaks · Регистрация: 26.04.2019

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

Написать функцию, которая проверяет, состоят ли два заданных списка из одних и тех же элементов (независимо от порядка их расположения)

Python
1
2
3
4
5
6
def check(lst_1, lst_2):       
        
    for item in lst_1:
        if not item in lst_2:
            return 'Not the same elements'
    return 'They consist from the same elements'

@nullxdth · 16.05.2019, 18:35

Lisp
1
2
(defun compare (xs ys)
  (tree-equal (sort xs #'<) (sort ys #'<)))

Python
1
2
def compare(xs, ys):
    return len(xs) == len(ys) and sorted(xs) == sorted(ys)

len в Python для оптимизации добавил. List в питоне - это не лист, а вектор. Размер за константу берётся.

Добавлено через 2 минуты
Hrizofilaks, твой код не будет работать на последовательностях с несколькими одинаковыми элементами.

Добавлено через 6 минут
Правда с сортировкой тоже есть свои проблемы - пример на Lisp работает только с числами. Надо какой-то странный компаратор писать, основанный на интроспекции типов и решать проблемы как сравнивать объекты разных типов.

@_sg · 16.05.2019, 18:43

как вариант:

Lisp
1
2
3
4
5
6
7
(defun same-elms (w v)
  (null (set-exclusive-or w v)))
 
> (same-elms '(4 0 1 2) '(2 0 1 3))
NIL
> (same-elms '(0 1 2) '(2 0 1))
T

@nullxdth · 16.05.2019, 18:49

Короче, подумалт

Сообщение от _sg

ак вариант:

Так ведь:

Lisp
1
(null (set-exclusive-or '(0 1 2) '(1 2 0 1))) ; T

@_sg · 16.05.2019, 18:50

Lisp
1
2
3
4
5
6
7
(defun same-elms (w v)
  (not (set-exclusive-or w v)))
 
> (same-elms '(4 0 1 2) '(2 0 1 3))
NIL
> (same-elms '(0 1 2) '(2 0 1))
T

@nullxdth · 16.05.2019, 18:51

Подумал. Вот такое решение видится нормальным:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun check (xs ys)
  (flet ((make-count-table (xs)
           (let ((table (make-hash-table :test #'equal)))
             (dolist (x xs table)
               (incf (gethash x table 0))))))
    (let ((xs-table (make-count-table xs))
          (ys-table (make-count-table ys)))
      (maphash (lambda (element count)
                 (multiple-value-bind (y-count y-present-p) (gethash element ys-table)
                   (unless (and y-present-p (= count y-count))
                     (return-from check))))
               xs-table)
      t)))

Основанным на эквивалентности.

@_sg · 16.05.2019, 18:57

имеется ввиду множество элементов (set)

Добавлено через 6 минут
как вариант:

Lisp
1
2
3
4
5
6
7
8
(defun exact-elms (w v)
  (loop for a in (intersection w v)
        always (= (count a w) (count a v))))
 
> (exact-elms '(0 1 2) '(2 0 1 1))
NIL
> (exact-elms '(1 0 1 2) '(2 0 1 1))
T

@korvin_ · 16.05.2019, 19:07

Сообщение от nullxdth

Основанным на эквивалентности.

Можно ж test-функцию вынести в ключевой параметр функции check.

@Catstail · 16.05.2019, 19:17

HomeLisp:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun comp-list (list1 list2)
  (equalset (setof list1) (setof list2)))
 
==> COMP-LIST
 
(comp-list '(0 1 2) '(2 2 1 0 0))
 
==> T
 
(comp-list '(0 1 2) '(2 2 1 7 0))
 
==> NIL

@_sg · 16.05.2019, 19:26

варианты:

Lisp
1
2
3
4
5
6
7
(defun same-elms (w v)
  (not (set-exclusive-or w v :test #'equalp)))
 
> (same-elms '(0 1 2 (a b)) '(2 0 1 (a c)))
NIL
> (same-elms '(0 1 2 (a b)) '(2 0 1 1 (a b) (a b)))
T

Lisp
1
2
3
4
5
6
7
8
9
(defun exact-elms (w v)
  (loop for a in (intersection w v :test #'equalp)
        always (= (count a w :test #'equalp)
                  (count a v :test #'equalp))))
 
> (exact-elms '(1 0 1 2 (a b)) '(2 0 1 1 (a b) (a b)))
NIL
> (exact-elms '(1 0 1 2 (a b)) '(2 0 1 1 (a b)))
T

@nullxdth · 16.05.2019, 19:27

Сообщение от korvin_

Можно ж test-функцию вынести в ключевой параметр функции check.

Верно. Так и надо сделать.

Глупая я голова. xs может быть сабсетом ys. Вот так вот надо:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun check (xs ys &key (test #'equal))
  (flet ((make-count-table (xs)
           (let ((table (make-hash-table :test test)))
             (dolist (x xs table)
               (incf (gethash x table 0))))))
    (let ((xs-table (make-count-table xs))
          (ys-table (make-count-table ys)))
      (when (= (hash-table-count xs-table)
               (hash-table-count ys-table))
        (maphash (lambda (element count)
                   (multiple-value-bind (y-count y-present-p) (gethash element ys-table)
                     (unless (and y-present-p (= count y-count))
                       (return-from check))))
                 xs-table)
        t))))

@Hrizofilaks · 16.05.2019, 20:16 **[ТС]**

nullxdth, А что в двух словах там происходит и как передать аргументы?

Добавлено через 2 минуты

Lisp
1
2
3
4
5
6
(defun check (w v)
  (loop for a in (intersection w v :test #'equalp)
        always (= (count a w :test #'equalp)
                  (count a v :test #'equalp))))
        
(print (check '(1 0 1 2 (a b)) '(2 0 1 1 (a b) (a b))))

Почему NIL?

@Catstail · 16.05.2019, 20:35

Непонятно, в чем существенная сложность задачи...

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 diflist (x y)
   (cond ((null y) x)
         (t (diflist (remove (car y) x) (cdr y)))))
 
==> DIFLIST
 
(diflist '(1 2 3) '(2 3))
==> (1)
 
(defun subset (x y) (null (diflist x y)))
 
==> SUBSET
 
(subset '(1 2 3) '(1 2))
==> NIL
 
(subset '(1 2 3) '(1 2 3 5))
==> T
 
(defun equalset (x y)
  (and (subset x y) (subset y x)))
 
==> EQUALSET

@nullxdth · 16.05.2019, 21:26

Сообщение от Hrizofilaks

Пноочему NIL?

Так списки-то разные. В одном списке один '(a b), в другом - два.
Если нужно поведение без учёта количества элементов, т.е. поработать со списками как с множествами, то решение от _sg самое то.

Lisp
1
2
3
4
(defun check (xs ys &key (test #'equal))
  (not (set-exclusive-or xs ys :test test)))
 
(check '(1 0 1 2 (a b)) '(2 0 1 1 (a b) (a b))) ; T

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .