9 Множества и деревья

Множества

В Прологе, в отличие от некоторых императивных языков программирования, нет такой встроенной структуры данных как множества. Однако это понятие можно реализовать это понятие, опираясь на имеющиеся стандартные домены. Под множеством можно понимать список, который не содержит повторных вхождений элементов, то есть в множестве любое значение не может встречаться более одного раза. Можно разработать предикаты, которые реализуют основные теоретико-множественные операции.

Предикат превращает произвольный список в множество. Для этого удалим повторные вхождения элементов, для чего воспользуемся предикатом DeleteAll. Два аргумента – исходный и выходной список.

list_set([],[]). /* пустой список является множеством

в нашем понимании */

list_set ([H|T],[H|T1]) :–

delete_all(H,T,T2),

/* T2 — результат удаления

вхождений первого элемента

исходного списка H из хвоста T */

list_set (T2,T1).

/* T1 — результат удаления

повторных вхождений элементов

из списка T2 */

Можно реализовать каждую операцию так, чтобы в результате гарантированно получалось множества.

Предикат, проверяющий принадлежность элемента списку.

member3(X,[X|_]) :- !.

member3(X,[_|T]) :- member3(X,T).

Объединения двух множеств A, B. Три параметра: первый – множество А, второй – множество В, третий – выходное множество. В других операция аналогично.

union([ ],S2,S2). /* результатом объединения

пустого множества со множеством S2

будет множество S2 */

union([H|T],S2,S):–

member3(H,S2),

/* если голова первого

множества H принадлежит второму

множеству S2, */

!,

union(T,S2,S).

/* то результатом S будет

объединение хвоста первого

множества T и второго

множества S2 */

union([H |T],S2,[H|S]):–

union(T,S2,S).

/* в противном случае результатом

будет множество, образованное

головой первого множества H

и хвостом, полученным объединением

хвоста первого множества T

и второго множества S2 */

Пересечение множеств.

intersection([],_,[]). /* в результате пересечения

пустого множества с любым

множеством получается пустое

множество */

intersection([H|T1],S2,[H|T]):–

member3(H,S2),

/* если голова первого множества H

принадлежит второму множеству S2 */

!,

intersection(T1,S2,T).

/* то результатом будет множество,

образованное головой первого

множества H и хвостом, полученным

пресечением хвоста первого

множества T1 со вторым

множеством S2 */

intersection([_|T],S2,S):–

intersection(T,S2,S).

/* в противном случае результатом

будет множество S, полученное

объединением хвоста первого

множества T со вторым

множеством S2 */

Разность множеств.

minus([],_,[]). /* при вычитании любого множества

из пустого множества получится пустое

множество */

minus([H|T],S2,S):–

member3(H,S2),

/* если первый элемент первого

множества H принадлежит второму

множеству S2*/

!,

minus(T,S2,S).

/* то результатом S будет разность

хвоста первого множества T

и второго множества S2 */

minus([H|T],S2,[H|S]):–

minus(T,S2,S).

/* в противном случае, результатом

будет множество, образованное

первым элементом первого

множества H и хвостом, полученным

вычитанием из хвоста первого

множества T второго множества S2 */

Другой вариант через разность.

intersection2(A,B,S):–

minus(A,B,A_B), /*A_B=A\B */

minus(A,A_B,S). /* S = A\A_B = A\(A\B) */

Предикат проверяющий является ли множество подмножеством другого.

subset([],_). /* пустое множество является

подмножеством любого множества */

subset([H|T],S):– /* множество [H|T] является

подмножеством множества S */

member3(H,S), /* если его первый элемент H

принадлежит S */

subset(T,S). /* и его хвост T является

подмножеством множества S */

Тот же предикат через операции объединение и пересечение.

subsetU(A,B):–

union(A,B,B). /* объединение множеств

совпадает со вторым множеством */

subsetI(A,B):–

intersection(A,B,A).

/* пересечение множеств

совпадает с первым множеством*/

Проверка совпадений двух множеств.

equal(A,B):– /* множество A совпадает

со множеством B, */

subset(A,B), /* если множество A содержится

во множестве B */

subset(B,A). /* и множество B является

подмножеством множества A*/

Проверка на собственное подмножество.

Prop_subset(A,B):–

subset(A,B),

/* множество A содержится

во множестве B */

not(equal(A,B)).

/* множества A и B не совпадают*/

Симметрическая разность – множество, чьи элементы принадлежат первому множеству и не принадлежат второму и наоборот.

Sim_minus(A,B,SM):–

minus(A,B,A_B), /* A_B — это разность

множеств A и B */

minus(B,A,B_A), /* B_A — это разность

множеств B и A */

union(A_B,B_A,SM). /* SM — это объединение

множеств A_B и B_A */

Дополнение. Для определенности, возьмем в качестве универсального множества множество цифр ({0,1,2,3,4,5,6,7,8,9}).

supp(A,D):–

U=[0,1,2,3,4,5,6,7,8,9],

minus(U,A,D). /* D — это разность

универсального множества U

и множества A */

Имея дополнение, можно выразить операцию объединения через пересечение и дополнение, или, наоборот, операцию пересечения через объединение и дополнение, используя законы де Моргана.

unionI(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

intersection(A_,B_,A_B),

/* A_B — это пересечение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */

intersectionU(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

union(A_,B_,A_B), /* A_B — это объединение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */

Деревья

Деревами называется граф, у которого одна вершина корневая, а остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины. Листом дерева называется вершина, не имеющая сыновей. Кроной дерева называется совокупность всех листьев. Высотой дерева называется наибольшая длина пути от коня к листу. Рекурсивное определение бинарного дерева: Дерево либо пусто, либо состоит из корня, а также левого и правого поддеревьев, которые в свою очередь так же являются бинарными деревьями. В Прологе можно разработать предикаты для организации работы с деревьями.

DOMAINS

tree=empty;tr(i,tree,tree)

/* дерево либо пусто, либо

состоит из корня (целого числа),

левого и правого поддеревьев,

также являющихся деревьями */

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

tree_member(X,tr(X,_,_)):-!. /* X - является корнем

дерева */

tree_member(X,tr(_,L,_)):-

tree_member(X,L),!. /* X принадлежит

левому поддереву */

tree_member(X,tr(_,_,R)):-

tree_member(X,R). /* X принадлежит

правому поддереву */

Пример. Предикат, который будет заменять в дереве все вхождения одного значения на другое. У предиката будет четыре аргумента: три входных (значение, которое нужно заменять; значение, которым нужно заменять; исходное дерево ), четвертым - выходным - аргументом будет дерево, полученное в результате замены всех вхождений первого значения на второе.

tree_replace(_,_,empty,empty). /* пустое дерево

остается пустым деревом*/

tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):-

/* корень содержит заменяемое

значение X*/

!,tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):-

/* корень не содержит

заменяемое значение X */

tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

Пример. Предикат, подсчитывающий общее количество вершин дерева . У него будет два параметра. Первый (входной) параметр - дерево , второй (выходной) - количество вершин в дереве.

tree_length (empty,0). /* В пустом дереве

нет вершин */

tree_length(tr(_,L,R),N):-

tree_length (L,N1),

/* N1 - число вершин

левого поддерева */

tree_length (R,N2),

/* N2 - число вершин

правого поддерева */

N=N1+N2+1. /* число вершин

исходного дерева

получается сложением

N1, N2 и единицы */

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

tree_leaves(empty,0). /* в пустом дереве

листьев нет */

tree_leaves(tr(_,empty,empty),1):-!.

/* в дереве с одним корнем -

один лист */

tree_leaves(tr(_,L,R),N):-

tree_leaves(L,N1),

/* N1 - количество листьев

в левом поддереве */

tree_leaves(R,N2),

/* N2 - количество листьев

в правом поддереве */

N=N1+N2.

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

tree_sum (empty,0). /* В пустом дереве

вершин нет */

tree_sum(tr(X,L,R),N):-

tree_sum (L,N1),

/* N1 - сумма элементов

левого поддерева */

tree_sum (R,N2),

/* N2 - сумма элементов

правого поддерева */

N=N1+N2+X. /* складываем N1, N2

и корневое значение */

Пример. Создадим предикат, позволяющий вычислить высоту дерева . Напомним, что высота дерева - это наибольшая длина пути от корня дерева до его листа . Предикат будет иметь два параметра. Первый (входной) - дерево , второй (выходной) - высота дерева , помещенного в первый параметр.

tree_height(empty,0). /* Высота пустого

дерева равна нулю */

tree_height(tr(_,L,R),D) :-

tree_height(L,D1),

/* D1 - высота левого

поддерева */

tree_height(R,D2),

/* D2 - высота правого

поддерева */

max(D1,D2,D_M),

/* D_M - максимум из высот

левого и правого поддеревьев */

D=D_M+1.

/* D - высота дерева получается

путем увеличения числа D_M

на единицу*/

Двоичные справочники – особый вид бинарных деревьев. В двоичном справочнике все значения входящие в левое поддерево меньше значения корня, в а значения в правом поддереве больше корня. Левое и правое поддеревья так же являются двоичными справочниками. Такие деревья упорядочены слева направо.

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

tree_member2(X,tr(X,_,_)):-!. /* X - корень

дерева */

tree_member2(X,tr(K,L,_)):-

X<K,!,

tree_member2(X,L).

/* X - принадлежит

левому поддереву */

tree_member2(X,tr(K,_,R)):-

X>K,!,

tree_member2(X,R).

/* X - принадлежит

правому поддереву */

Предикат добавляющий в двоичный справочник новое значение.

tree_insert(X,empty,tr(X,empty,empty)).

/* вставляем X в пустое дерево,

получаем дерево с X в корневой

вершине,пустыми левым и

правым поддеревьями */

tree_insert(X,tr(X,L,R),tr(X,L,R)):-!.

/* вставляем X в дерево

со значением X в корневой

вершине, оставляем исходное

дерево без изменений */

tree_insert(X,tr(K,L,R),tr(K,L1,R)):-

X<K,!,

tree_insert(X,L,L1).

/* вставляем X в дерево

с большим X элементом в

корневой вершине, значит,

нужно вставить X в левое

поддерево исходногодерева */

tree_insert(X,tr(K,L,R),tr(K,L,R1)):-

tree_insert(X,R,R1).

/* вставляем X в дерево

с меньшим X элементом

в корневой вершине, значит,

нужно вставить X в правое

поддерево исходного дерева */

Предикат генерирующий дерево, являющееся двоичным справочником и состоящее из заданного количества вершин в которых размещаются случайные целые числа.

tree_gen(0,empty):-!. /* ноль вершин

соответствует пустому дереву */

tree_gen (N,T):-

random(100,X),

/* X - случайное число

из промежутка [0,100) */

N1= N-1,

tree_gen (N1,T1),

/* T1 - дерево, имеющее

N-1 вершин */

tree_insert(X,T1,T). /* вставляем X

в дерево T1 */

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

Предикат удаляющий заданное значение из двоичного справочника. Опишем вспомогательный предикат удаляющий минимальный элемент двоичного справочника.

tree_del_min(tr(X,empty,R), R, X).

/* Если левое поддерево пусто,

то минимальный элемент - корень,

а дерево без минимального

элемента - это правое поддерево.*/

tree_del_min(tr(K,L,R), tr(K,L1,R), X):-

tree_del_min(L, L1, X).

/* Левое поддерево не пусто,

значит, оно содержит минимальное

значениевсего дерева,

которое нужно удалить */

tree_delete(X,tr(X,empty,R), R):-!.

/* X совпадает с корневым

значением исходного дерева,

левое поддерево пусто */

tree_delete (X,tr(X,L,empty), L):-!.

/* X совпадает с корневым

значением исходного дерева,

правое поддерево пусто */

tree_delete (X,tr(X,L,R), tr(Y,L,R1)):-

tree_del_min(R,R1, Y).

/* X совпадает с корневым

значением исходного

дерева, причем ни левое, ни

правое поддеревья не пусты */

tree_delete (X,tr(K,L,R), tr(K,L1,R)):-

X<K,!,

tree_delete (X,L,L1).

/* X меньше корневого значения

дерева */

tree_delete (X,tr(K,L,R), tr(K,L,R1)):-

tree_delete (X,R,R1).

/* X больше корневого значения

дерева */

Предикат, преобразующий произвольный список в двоичный справочник.

list_tree([],empty). /* Пустому списку

соответствует пустое дерево */

list_tree([H|T],Tr):-

list_tree(T,Tr1),

/* Tr1 - дерево, построенное

из элементов хвоста

исходного списка */

tree_insert(H,Tr1,Tr).

/* Tr - дерево, полученное

в результате вставки

головы списка в дерево Tr1 */

Предикат, преобразующий двоичный справочник в список.

tree_list(empty,[]). /* Пустому дереву

соответствует пустой список */

tree_list(tr(K,L,R),S):-

tree_list(L,T_L),

/* T_L - список,

построенный из элементов

левого поддерева */

tree_list(R,T_R),

/* T_L - список,

построенный из элементов

правого поддерева */

conc(T_L,[K|T_R],S).

/* S - список, полученный

соединением списков T_L

и [K|T_R] */

Сортировка списка.

sort_listT(L,L_S):-

list_tree(L,T),

/* T- двоичный справочник,

построенный из элементов

исходного списка L */

tree_list(T,L_S).

/* L_S - список, построенный из

элементов двоичного

справочника T */

Так как в двоичном справочнике все элементы различны, при переписывании списка в двоичный справочник и обратно повторяющиеся элементы будут из него удалены. Неизменным останется количество элементов списка, только если все его элементы были различны.