Алгоритмы и структуры данных для начинающих: множества

Множество — это коллекция, которая реализует основные математические операции над множествами: пересечения (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 — количество элементов переданного и текущего множеств соответственно.

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

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

data_structures_031

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

data_structures_032

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

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

[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 — количество элементов переданного и текущего множеств соответственно.

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

data_structures_033

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

[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 — количество элементов переданного и текущего множеств соответственно.

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

data_structures_034

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

[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 — количество элементов переданного и текущего множеств соответственно.

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

data_structures_035

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

[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»