7.6. Представление и обработка множеств
Множество - одна из наиболее важных структур данных, используемых как в математике, так и в программировании. Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит в множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Самой фундаментальной операцией над множествами является определение того, принадлежит некоторый элемент данному множеству или нет.
Не должно вызывать удивления, что множества удобно представлять в виде списков. Список может содержать произвольные элементы, включая другие списки, и над списками можно определить предикат принадлежности. Однако условимся, что когда мы представляем множество в виде списка, такой список содержит только по одному элементу на каждый объект, принадлежащий множеству. При работе со списками без повторяющихся элементов упрощаются некоторые операции, такие, как удаление элементов. Итак, нам предстоит иметь дело только со списками без повторяющихся элементов. Предикаты, рассматриваемые ниже, соблюдают это свойство и опираются на него.
Над множествами обычно определяется следующий набор операций (мы будем применять и общепринятые математические обозначения для тех читателей, кто к ним привык):
Принадлежность множеству: X∈Y
X принадлежит некоторому множеству Y, если X является одним из элементов Y.
Пример: а∈{с,а,t}.
Включение: X⊂Y
Множество Y включает в себя множество X, если каждый элемент множества X является также элементом Y. Множество Y может содержать некоторые элементы, которых нет в X.
Пример: {x,r,u}⊂{p,q,r,f,t,u,v,w,x,y,z}.
Пересечение: X∩Y
Пересечением множеств X и Y является множество, содержащее те элементы, которые одновременно принадлежат X и Y.
Пример: {r,a,p,i,d} ∩ {p,i,c,t,u,r,e} = {r,i,p}.
Объединение: X ∪ Y
Объединением множеств X и
