LINUX.ORG.RU

[common lisp] Объединить множества с отношением поглощения

 


0

0

Есть ли в лиспе такая функция, которая позволяет объединять два множества, образовывая новое, которое представляет собой отношение поглощения двух предыдущих?

Например,

(defvar p1 (list (list 1 2)
   (list 3)
   (list 4 5)
   (list 6)
   (list 7))

(defvar p2 (list (list 1)
   (list 2 3 4)
   (list 5)
   (list 6)
   (list 7)))

(defvar p-after-merging-p1-and-p2 (list
   (list 1 2 3 4 5)
   (list 6)
   (list 7)))

Эта задача из теории конечных автоматов на нахождение нетривиальных конгруэнций.

В лиспе есть функция merge, но я не понял, какой предикат туда надо вставить, чтобы добиться моего результата.

★★

Мне пока даже непонятно, что должно получиться в итоге. Каким образом вы объединили множества (1 2), (2 3 4), (4 5)? Ведь ни одно из них не вложено в другое.

dmitry_vk ★★★
()

Попытайтесь сформулировать как вы видете алгоритм такого вот объеденения.

Второе, у вас там скобочек не хватает, в районе p1

catap ★★★★★
()

> В лиспе есть функция merge, но я не понял, какой предикат туда надо вставить, чтобы добиться моего результата.

Для этой задачи merge не подходит, merge выполняет слияние двух отсортированных последовательностей. В твоём случае нужно будет что-то более хитрое. ИМХО если есть алгоритм, проще написать это самому.

slav ★★
()
Ответ на: комментарий от dmitry_vk

Мне пока даже непонятно, что должно получиться в итоге

аналогично. по отношению поглощения множеств нашёл только одну статью 1976 года, разбираться в которой ради ответа на этот вопрос - лень

jtootf ★★★★★
()
Ответ на: комментарий от dmitry_vk

Алгоритм следующий: если есть хотя бы один элемент одного множества есть в другом множестве, то эти множества следует объединить. И так до конца, пока не останется множеств, в которых есть дублирующиеся элементы в двух множествах.

bk_ ★★
() автор топика
Ответ на: комментарий от catap

Предыдущее мое сообщение получилось невнятное.

Есть два множества, которые нужно объединить. Элементы у них всегда одинаковые.

Если в подмножестве первого множества есть элемент, который встречается в подмножестве другого множества, эти подмножества надо объединить и удалить дублирующиеся элементы в получившемся подмножестве.

Так надо делать со всеми подмножествами исходных двух множеств.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

Очевидно же, что нет. Лень писать? Ищи библиотеку для работы с автоматами.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.