Как найти объединение множеств в информатике

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

̶
Здравствуй Максим!

̶
Здравствуйте! Проверьте, чтобы ваши соседи по парте были готовы к уроку. И мы
начинаем.

Прослушайте
название пар множеств и попытайтесь заметить, что повторяется в
каждой паре.

Животные
и герои мультфильмов;

Рыбы
и птицы;

Материки
и части света;

Звёзды
и планеты.

Ну,
что заметили? Конечно, повторялся слово «и».

Если
в названии множества есть союз «И», то каждый его элемент должен находиться
на пересечении двух множеств, т.е. находиться одновременно в двух
множествах. Другими словами мы можем сказать, что пересечение множеств
– это их общая часть.

А
теперь задание.

Необходимо
разместить элементы по своим множествам.

Давайте
посмотрим, что за элементы. Так это имена мальчиков и девочек: Коля, Ваня,
Даша, Игорь, Катя, Саша, Дима, Юля, Ира, Женя. Будем размещать имена мальчиков
в синий прямоугольник, а девочек – в розовый. Ага! Так ведь Сашей и Женей могут
звать как мальчиков, так и девочек. Значит, эти два имени будут находиться
сразу в двух множествах, т.е. на пересечении двух множеств.

Итак,
Коля, Ваня – это мальчики, помещаем эти элементы во множество имён мальчиков.
Даша – имя девочки, помещаем в розовый прямоугольник, где находятся имена
девочек. Игорь – имя мальчика, Катя – имя девочки. Саша, так могут звать и
мальчика, и девочку, значит, этот элемент будет находиться на пересечении
двух множеств. Дима – элемент из множества имён мальчиков. Юля, Ира,
конечно элементы из множества имён девочек. И последнее имя, Женя, это имя
могут иметь как девочки, так и мальчики. Значит, этот элемент будет находиться на
пересечении двух множеств.

Теперь
все имена находятся в своих множествах.

А
сейчас я прочитаю названия ещё нескольких пар множеств, а вы попытайтесь
заметить, что повторяется в этих парах.

Яблоки
или груши;

Полевые
или садовые цветы;

Попугаи
или морские свинки;

Рабочие
или выходные дни.

Заметили,
что повторялось в парах множеств? Конечно, это слово «или».

Посмотрите
ещё раз на названия множеств.

Например,
яблоки или груши. А ведь эти множества можно объединить в одно с общим
названием «фрукты» и все элементы будут располагаться в одном новом
множестве.

 Попугаи
или морские свинки. Их можно объединить во множество с названием

«домашние
животные» и все попугаи, и все морские свинки будут находиться в новом
множестве.

Значит,
если в названии множества есть слово «или», то его элемент может
находиться в любом множестве и тогда происходит объединение множеств, т.е. эти множества
объединяются.

Давайте
рассмотрим два множества: домашние животные, дикие животные.

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

Множество
дикие животные состоит из следующих элементов: бегемот, леопард, волк, лев.

Какой
общий признак у элементов этих двух множеств? Элементы
каждого из них относятся с животному миру. Значит, можно, объединив эти
множества, создать новое множество под названием животные. Теперь
все элементы находятся в одном множестве.

А
теперь, конечно, задание.

Распределить
элементы по множествам, объединить их и придумать
название для нового множества.

Итак,
смотрим на элементы. Ага, у нас два множества: множество стульев
и множество столов. Распределяем элементы по множествам. Все элементы
стулья во множество стульев, а все элементы столы во множество столов.

Объединяем
множества. Какое название будет у нашего нового множества?
Множество мебели.

Давайте
ещё раз определим разницу между пересечением и объединением множеств.

Если
в названии множества есть слово «И», то это пересечение,
и каждый элемент должен находиться на пересечении двух множеств.

Если
в названии множества есть слово «или», то его элемент может
находиться в любо области объединённых множеств.

Я
надеюсь, что вы поняли разницу между пересечением и объединением
множеств. А давайте проверим?

Итак,
перед вами рисунок с тремя множествами.

Множество
учеников, которые любят математику, множество учеников, которые любят
информатику и множество всех учеников. Но, среди учеников есть и такие, которые
любят и математику и информатику. Значит, эти два множества пересекаются
и одновременно они являются подмножеством множества всех
учеников. А теперь появляются элементы во множествах.

Используя
полученные знания сегодня на уроке, будем отвечать на вопросы. А все ответы
хранятся на этом рисунке, главное внимательно слушать вопросы и внимательно
смотреть на рисунок.

Первый
вопрос:

Сколько
учеников любят математику? Считаем их во множестве учеников, которые любят
математику, и не забываем посчитать тех учеников, которые находятся на пересечении
двух множеств учеников, которые любят и математику, и информатику. Считаем. Их
шесть.

Сколько
учеников любят информатику? Считаем их во множестве учеников, которые любят
информатику и опять считаем тех учеников, которые находятся на пересечении
двух множеств. Считаем. Их пять.

Сколько
учеников любят и математику, и информатику? Будем считать тех учеников, которые
находятся на пересечении двух множеств. Их три.

Сколько
учеников любят или математику или информатику? Если используется слово «или»,
значит элементы находятся в любом месте множеств за исключением любителей двух
предметов сразу. Значит, считаем учеников и в первом множестве и во втором, но
не включаем тех, кто находится в пересечении. Их пять.

Сколько
учеников любят только математику? Любят математику только те, которые находятся
во множестве учеников, которые любят математику. Ученики, которые находятся на
пересечении двух множеств, сюда относится не будут, т.к. они любят и
математику, и информатику. Итак, считаем и получается, что 3 ученика любят
только математику.

Сколько
учеников любят только информатику? Опять, учеников, которые находятся на пересечении
двух множеств, считать не будем. Любителей информатики двое.

Сколько
учеников не любят математику? Надо посчитать их во множестве учеников, которые
любят информатику, кроме тех, которые находятся на пересечении
множеств, т.к. эти ученики любят информатику и математику. А так же надо
посчитать тех учеников, которые находятся во множестве всех учеников, т.к. они
не любят математику. Их всего 5.

Всем
спасибо за отличную работу. Теперь я точно понял, что хочу быть учителем!

Тебе
спасибо, Максим. Тему объяснил хорошо. До свидания! А мы ещё сделаем выводы.

Итак.

Множество
– это объединение некоторых объектов (элементов) в группу по определённым
признакам.

Множество
может быть подмножеством другого множества. Например: множество
собак является подмножеством множества домашние животные.

Множества
могут пересекаться. Например: множество чисел, которые делятся на
2, и множество чисел, которые делятся на 3, пересекаются, т.к. числа, например,
6 и 12 делится и на 2, и на 3.

Множества
могут и не пересекаться. Например: множество телефонов и
множество цветов.

И
множества могут объединяться. Например: множество рабочих дней
недели и множество выходных можно объединить в одно множество дней недели.

Выводы
сделаны, и я желаю вам успехов при выполнении заданий!

Множество — это коллекция, которая реализует основные математические операции над множествами: пересечения (intersection), объединение (union), разность (difference) и симметрическая разность (symmetric difference). Каждый из алгоритмов мы разберем в соответствующем разделе.

Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, связный список, оценка сложности алгоритма и сортировка.

Множество

В математике множества — это коллекции объектов, у которых есть что-то общее. Например, мы можем объявить множество четных положительных целых чисел:

[2, 4, 6, 8, 10, ...]

Или множество нечетных положительных целых:

[1, 3, 5, 7, 9, ...]

В этих двух множествах нет общих элементов. Давайте теперь посмотрим на множество делителей числа 100:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

Теперь мы можем узнать, какие делители числа 100 — нечетные, просто глядя на множество нечетных чисел и на множество делителей и выбирая те из чисел, которые присутствуют в обоих. Мы также можем ответить на вопрос: «Какие нечетные числа не являются делителями ста?» или «Какие положительные целые, четные или нечетные, не являются делителями ста?».

На первый взгляд это кажется не очень полезным, но это искусственный пример. Предположим, что у нас есть множество всех работников предприятия и множество работников, прошедших ежемесячную проверку. Тогда мы с легкостью сможем ответить на вопрос: «Кто из работников не прошел проверку?».

Мы также можем добавить различные множества и построить более сложный запрос, например: «Кто из штатных работников отдела продаж, имеющих корпоративную кредитную карточку, не прошел обязательный курс повышения квалификации?».

Класс Set

Класс Set реализует интерфейс IEnumerable и принимает аргумент типа, который является наследником IComparable, так как для работы алгоритмов нужна проверка элементов на равенство.

Элементы нашего множества будут храниться в экземпляре стандартного класса .NET List, но на практике для хранения обычно используются древовидные структуры, например, двоичное дерево поиска. Выбор внутреннего представления будет влиять на сложность алгоритмов работы с множеством. К примеру, при использовании списка метод Contains будет выполняться за O(n) времени, в то время как множество, реализованное с помощью дерева, будет работать в среднем за O(log n) времени.

Кроме методов для работы с множеством класс Set также имеет конструктор, который принимает IEnumerable с начальными элементами.

public class Set : IEnumerable
    where T: IComparable
{
    private readonly List _items = new List();
 
    public Set()
    {
    }
 
    public Set(IEnumerable items)
    {
        AddRange(items);
    }
 
    public void Add(T item);
 
    public void AddRange(IEnumerable items);
 
    public bool Remove(T item);
 
    public bool Contains(T item);
 
    public int Count
    {
        get;
    }
 
    public Set Union(Set other);
 
    public Set Intersection(Set other);
 
    public Set Difference(Set other);
 
    public Set SymmetricDifference(Set other);
 
    public IEnumerator GetEnumerator();
 
    System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator();
}

Метод Add

• Поведение: Добавляет элементы в множество. Если элемент уже присутствует в множестве, бросается исключение InvalidOperationException.
• Сложность: O(n)

При реализации метода Add необходимо решить, будем ли мы разрешать дублирующиеся элементы. К примеру, если у нас есть мнжество:

[1, 2, 3, 4]

Если пользователь попытается добавить число 3, в результате получится:

[1, 2, 3, 3, 4]

В некоторых случаях это допустимо, но в нашей реализации мы не будем поддерживать дубликаты. Если представить, например, множество студентов колледжа, было бы нелогичным добавлять в него одного и того же студента дважды. На самом деле, попытка добавить элемент, который уже присутствует — скорее всего ошибка, и наша реализация класса Set воспринимает ее именно так.

Метод Add использует метод Contains, который будет рассмотрен далее.

public void Add(T item)
{
    if (Contains(item))
    {
        throw new InvalidOperationException(
"Item already exists in Set"
);
    }
 
    _items.Add(item);
}

Метод AddRange

• Поведение: Добавляет несколько элементов в множество. Если какой-либо из добавляемых элементов присутствует в множестве, или в добавляемых элементах есть дублирующиеся, выбрасывается исключение InvalidOperationException.
• Сложность: O(m·n), где m — количество вставляемых элементов и n — количество элементов множества.

public void AddRange(IEnumerable items)
{
    foreach (T item in items)
    {
        Add(item);
    }
}

Метод Remove

• Поведение: Удаляет указанный элемент из множества и возвращает true. В случае, если элемента нет, возвращает false.
• Сложность: O(n)

public bool Remove(T item)
{
    return _items.Remove(item);
}

Метод Contains

• Поведение: Возвращает true, если множество содержит указанный элемент. В противном случае возвращает false.
• Сложность: O(n)

public bool Contains(T item)
{
    return _items.Contains(item);
}

Метод Count

• Поведение: Возвращает количество элементов множества или 0, если множество пусто.
• Сложность: O(1)

public int Count
{
    get
    {
        return _items.Count;
    }
}

Метод GetEnumerator

• Поведение: Возвращает итератор для перебора элементов множества.
• Сложность: Получение итератора — O(1), обход элементов множества — O(n).

public IEnumerator GetEnumerator()
{
    return _items.GetEnumerator();
}
 
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return _items.GetEnumerator();
}

Алгоритмы

Метод Union

• Поведение: Возвращает множество, полученное операцией объединения его с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Объединение множеств — это множество, которое содержит элементы, присутствующие хотя бы в одном из двух.

Например, есть два множества (выделены красным):

При операции объединения выбираются элементы обоих множеств. Если элемент присутствует в обоих множествах, берется только одна его копия. Объединение двух множеств показано желтым цветом.

Такая диаграмма, наглядно показывающая операции над множествами, называется диаграммой Венна.

Другой пример с использованием множеств целых чисел:

[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]

public Set Union(Set other)
{
    Set result = new Set(_items);
 
    foreach (T item in other._items)
    {
        if (!Contains(item))
        {
            result.Add(item);
        }
    }
 
    return result;
}

Метод Intersection

• Поведение: Возвращает множество, полученное операцией пересечения его с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

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

Или, используя целые числа:

[1, 2, 3, 4] intersect [3, 4, 5, 6] = [3, 4]

public Set Intersection(Set other)
{
    Set result = new Set();
 
    foreach (T item in _items)
    {
        if (other._items.Contains(item))
        {
            result.Add(item);
        }
    }
 
    return result;
}

Метод Difference

• Поведение: Возвращает множество, являющееся разностью текущего с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Разность множеств — это все элементы, которые содержатся в одном множестве (том, у которого вызывается метод), но не содержатся в другом (том, которое передается аргументом). Диаграмма Венна для разности множеств будет выглядеть так:

Или, используя целые числа:

[1, 2, 3, 4] difference [3, 4, 5, 6] = [1, 2]

public Set Difference(Set other)
{
    Set result = new Set(_items);
 
    foreach (T item in other._items)
    {
        result.Remove(item);
    }
 
    return result;
}

Метод Symmetric Difference

• Поведение: Возвращает множество, являющееся симметрической разностью текущего с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Симметрическая разность — это все элементы, которые содержатся только в одном из рассматриваемых множеств. Диаграмма Венна для симметрической разности будет выглядеть так:

Или, используя целые числа:

[1, 2, 3, 4] symmetric difference [3, 4, 5, 6] =
[1, 2, 5, 6]

Вы, возможно, заметили, что симметрическая разность — это «пересечение наоборот». Учитывая это, давайте попробуем найти ее, используя уже имеющиеся операции.

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

Или, если рассматривать по шагам:

[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]

[1, 2, 3, 4] intersection [3, 4, 5, 6] = [3, 4]

[1, 2, 3, 4, 5, 6] set difference [3, 4] = [1, 2, 5, 6]

Что дает нам нужный результат: [1, 2, 5, 6].

public Set SymmetricDifference(Set other)
{
    Set union = Union(other);
    Set intersection = Intersection(other);
 
    return union.Difference(intersection);
}

Метод IsSubset

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

[1, 2, 3] is subset [0, 1, 2, 3, 4, 5] = true

В то время, как:

[1, 2, 3] is subset [0, 1, 2] = false

Дело в том, что эту проверку можно провести, используя имещиеся методы. К примеру:

[1, 2, 3] difference [0, 1, 2, 3, 4, 5] = []

Пустое множество в результате говорит нам о том, что все элементы первого множества содержатся во втором, а значит, первое является подмножеством второго. Другой способ проверить это:

[1, 2, 3] intersection [0, 1, 2, 3, 4, 5] =
[1, 2, 3]

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

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

Продолжение следует

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

_{Перевод статьи «The Set Collection»}

Объединение множеств знакомо каждому человеку. Оно встречается в математике. Программирование тоже «знакомо» с ним. Зная это, удается создавать качественный софт. Особенно тогда, когда речь заходит о сортировке или соединении.

В данной статье будет более подробно рассмотрены «массивы», а также операции над ними. В качестве базового языка используется Python. Он является одним из наиболее простых вариантов создания утилит.

Определение

Рассматриваемый компонент – это некая неупорядоченная совокупность уникальных неупорядоченных значений. Компонентами выступают любые некорректируемые объекты:

• числа;
• строки;
• символы.

Объединение множеств – простая операция. Но об этом позже. Отличительная их черта от массивов и списков – здесь не учитывается порядок следования значений.

Как создать

Перед рассмотрением объединения множеств их необходимо сначала создать. Сделать это удается присвоением переменной последовательности значений. «Перечень» указывается в {}.

Вот – пример, позволяющий создать множество целых чисел a. После – вывод содержимого на дисплей задействованного устройства:

Каждый элемент множества в последовательности уникален. Он не повторяется. Есть и такой способ создания соответствующего элемента кода, при котором применяется метод set. Аргументом в функции выступает набор данных или строчка с текстом. Вот пример:

Результат обработки исходного кода: заполнение нового массива уникальными символами из первоначально заданной строчки.

Генератор

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

В Питоне для этого используется цикл for:

Сортировка

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

Сначала стоит рассмотреть ситуацию, при которой компоненты имеют разные типы данных в пределах «массива информации». Они не сортируются. При print появится следующая запись:

При повторном запуске порядок поменяется. Это требуется тогда, когда компоненты разного типа перемешаны. Если же вывести только числа, получится такая ситуация:

Произошло упорядочивание информации. Если преобразовать результат в список, на экране появится надпись:

Стоит обратить внимание на следующие особенности:

1. Элементы будут храниться в памяти в упорядоченном виде, если они относятся к одному типу.
2. Для того, чтобы получить отсортированный список, лучше применять функцию sort. После объединение множеств будет упрощено.
3. Sort позволяет стопроцентно упорядочить информацию. Эта функция сделает код более понятным.

Теперь можно рассмотреть объединение множеств, а также иные операции над ними. Все это пригодится как новичку, так и опытному разработчику. База, без которой полноценное программирование не представляется возможным.

Операции

Можно выполнять различные действия не только с элементами мно жеств. Программирование позволяет управлять несколькими подобными «массивами данных». Для этого применяются разнообразные операции.

Объединение

Объединение двух множеств является базовой манипуляцией. Это – самый простой вариант. Результат объединения множеств a и b – это «массив неупорядоченных данных», который содержит в себе все компоненты, входящие в a и b соответственно.

Объединение между двумя множествами осуществляется:

• через оператор |;
• при помощи метода union().

Объединение множеств на картинке будет выглядеть так:

А вот объединение в виде программного кода. Пользователь может воспользоваться | для реализации поставленной задачи:

В консоли при выводе результата, который «объединили», появится:

А вот объединение, которое реализовано через функцию под названием union:

Пересечение

Объединение и пересечение – операции в математике, с которыми знакомятся еще во время обучения в школе. При пересечении результатом будет выступать «массив данных», который включает в себя компоненты, находящиеся сразу в двух множествах.

Реализация осуществляется через:

• оператор &;
• метод intersection.

Визуальное отличие соответствующей манипуляции от объединения можно четко представить. На изображении ниже – результат пересечения:

А вот – представление в программировании:

Разность

Когда пересечение множеств и объединение позади, можно рассмотреть иные варианты операций. Пример – разность.

Результатом разности двух множеств выступает «массив», в котором содержатся элементы, относящиеся только к одному из них. А именно – к первому. Реализация осуществляется при помощи:

• оператора — ;
• метода difference.

А вот – наглядный графический пример и коды, которые помогут добиться желаемого результата:

Симметрическая разность

При симметрической разности результатом называется «массив», которое включает в себя компоненты из обоих «массивов», но не те, что есть сразу в обоих. Здесь будет исключаться только пересечение.

Реализация:

• при помощи ^;
• через symmetric difference.

Наглядно ситуация выглядит так:

Добавление

Пересечение и объединение – это « только общее» или «сразу все». Есть еще и так называемое добавление. Оно помогает добавить все компоненты одного «массива» к другому. Для этого используется на первом объекте метод update.

Пустые «перечни»

Отдельное внимание стоит уделить пустым множествам. Это «массивы», которые «ничего не содержат». Для работы с ними лучше всего использовать set().

В математике пустым множеством называется «массив», которое не содержит ни одного элемента. Аксиома объемности указывает на то, что есть только один «массив» с подобным свойством. Выступает такой компонент в качестве своего тривиального подмножества. А вот своим элементом не является.

При объединении пустого множества a с b результатом будет служить последний «массив информации».

Отношения

Еще один момент, на который необходимо обратить внима ние – это отношения между «массивами». Для того, чтобы определять подмножества и надмножества, используются специальные функции. Они возвращают True или False. Итог зависит от результата обработки «команды».

Подмножество

Разбираясь я объединением множеств и иными операциями, нужно обратить внимание на подмножества. Для того, чтобы определить, является ли «массив» a подмножеством b, нужно вывести на экран результат обработки метода issubset.

Здесь не все компоненты из a присутствуют в b. Подобная ситуация вернет значение False.

Надмножество

При пересечении и объединении обычно не происходит вывод «истины» и «лжи» — только нового набора данных. Чтобы понять, является ли a надмножеством b, необходимо:

• вызвать метод под названием issuperset;
• отобразить на экране результат работы.

Здесь true будет из-за того, что все компоненты b присутствуют в a. Что-то схожее с пересечением (с пустым множеством и не только).

Frozen

Если корректировка «массива» не предусматривается, он будет иметь тип frozen. Значения тут нельзя удалить или добавить. Значит, объединение множеств фактически невозможно. Содержимое здесь остается статичным.

Пересечение и объединение, а также иные операции можно изучить в школьной программе. А лучше – закончить онлайн курсы по соответствующему направлению. Там объяснят, как называется «массив», который принадлежит хотя бы одному из заданных множеств и многое другое.

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!

Также, возможно, вам будет интересен следующий курс:

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

• Теория множеств без страха
• Об операциях с множествами без боли
• Множества вокруг нас
• Заключение

Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.

Теория множеств без страха

Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.

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

Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.

В этом определении есть три важных слова: «неупорядоченная», «дублирующихся» и «элементов». Эти слова точно передают суть и устройство множества. Если мы это запомним, то будем знать основную информацию о том, как работает эта структура данных.

Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.

---

Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.

Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.

---

Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.

Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.

Об операциях с множествами без боли

Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.

---

Пересечение множеств часто записывается с помощью такой нотации: X ∩ Y. Пересечение определяет, где два множества пересекаются. Другими словами, эта операция возвращает все элементы, которые входят в два множества. В нашем примере пересечение Set X и Set Y возвращает все книги, которые человек читал и которые есть у него дома. Хороший ключ к пониманию пересечения — ключевое слово «и». Мы получаем книги, которые человек читал и которые есть у него дома. Несмотря на то, что полученные с помощью пересечения книги существуют в двух множествах, мы не повторяем их, так как в множестве могут быть только уникальные элементы.

Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.

С помощью диаграммы Венна пересечение и объединение можно представить так:

---

Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.

Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.

---

Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X Y. Относительное дополнение X Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.

По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?

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

Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.

В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?

Правильное название для этого кейса — симметрическая разность множеств. Также употребляют термины «дизъюнктивное объединение» и «несвязное объединение». Симметрическая разность возвращает все элементы, которые входят в одно из множеств, но не входят в пересечение этих множеств. Пример на иллюстрации поможет разобраться с дизъюнктивным объединением.

---

В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).

Но не дайте сбить себя с толку!

Читайте также:
Что такое JVM? Знакомство с виртуальной машиной Java.

Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.

В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.

Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.

Множества вокруг нас

К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.

Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.

Вот пример на JavaScript.

var s = new Set();

s.add(2); 
// Set { 2}
s.add(45); 
// Set { 2, 45}
s.add(45); 
// Set { 2, 45}
s.add('hello world!'); 
// Set { 2, 45, 'hello world!' }

s.has(2); 
// true
s.has('cats'); 
// false

s.size; 
// 3

s.delete(45); 
// Set { 2, 'hello world!' }

s.has(45);    
// false

Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.

Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?

---

Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.

Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.

Но подождите, почему все операции с множествами выполняются так быстро? Как это возможно? Как оказалось, под капотом множества представляют собой хэши. Теперь вся информация собирается воедино. С хэш-таблицами знакомо большинство программистов, но почему с их помощью так удобно реализовывать множества?

Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.

Читайте также
Haskell — язык, позволяющий глубже понять программирование. Как он устроен и почему его выбирают разработчики?

Заключение

Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.

Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.

Никогда не останавливайтесь:
В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.