Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура  очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Давайте рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#.

На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность.

Set

Set

Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:

  • Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен.
  • Remove — удаление элемента из множества.
  • Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если элемент содержится в обоих множествах, он будет добавлен однократно.
  • Difference — разность множеств. Создается новое множество, включающее в себя все элементы множества А, которые не входят в множество В.
  • Intersection — пересечение множеств. Создается новое множество, включающее в себя все элементы входящие одновременно и в множество А, и в множество В.
  • Subset — проверка на подмножество. Чтобы быть подмножеством, все элементы множества А должны содержаться в множестве В. Тогда множество А является подмножеством множества В.

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

Множество

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Set
{
    /// <summary>
    /// Множество.
    /// </summary>
    /// <typeparam name="T"> Тип данных, хранимых во множестве. </typeparam>
    public class Set<T> : IEnumerable<T>
    {
        /// <summary>
        /// Коллекция хранимых данных.
        /// </summary>
        private List<T> _items = new List<T>();

        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count => _items.Count;

        /// <summary>
        /// Добавить данные во множество.
        /// </summary>
        /// <param name="item"> Добавляемые данные. </param>
        public void Add(T item)
        {
            // Проверяем входные данные на пустоту.
            if (item == null)
            {
                throw new ArgumentNullException(nameof(item));
            }

            // Множество может содержать только уникальные элементы,
            // поэтому если множество уже содержит такой элемент данных, то не добавляем его.
            if (!_items.Contains(item))
            {
                _items.Add(item);
            }
        }

        /// <summary>
        /// Удалить элемент из множества.
        /// </summary>
        /// <param name="item"> Удаляемый элемент данных. </param>
        public void Remove(T item)
        {
            // Проверяем входные данные на пустоту.
            if (item == null)
            {
                throw new ArgumentNullException(nameof(item));
            }

            // Если коллекция не содержит данный элемент, то мы не можем его удалить.
            if (!_items.Contains(item))
            {
                throw new KeyNotFoundException($"Элемент {item} не найден в множестве.");
            }

            // Удаляем элемент из коллекции.
            _items.Remove(item);
        }

        /// <summary>
        /// Объединение множеств.
        /// </summary>
        /// <param name="set1"> Первое множество. </param>
        /// <param name="set2"> Второе множество. </param>
        /// <returns> Новое множество, содержащее все уникальные элементы полученных множеств. </returns>
        public static Set<T> Union(Set<T> set1, Set<T> set2)
        {
            // Проверяем входные данные на пустоту.
            if (set1 == null)
            {
                throw new ArgumentNullException(nameof(set1));
            }

            if (set2 == null)
            {
                throw new ArgumentNullException(nameof(set2));
            }

            // Результирующее множество.
            var resultSet = new Set<T>();

            // Элементы данных результирующего множества.
            var items = new List<T>();

            // Если первое входное множество содержит элементы данных,
            // то добавляем их в результирующее множество.
            if (set1._items != null && set1._items.Count > 0)
            {
                // т.к. список является ссылочным типом, 
                // то необходимо не просто передавать данные, а создавать их дубликаты.
                items.AddRange(new List<T>(set1._items));
            }

            // Если второе входное множество содержит элементы данных, 
            // то добавляем из в результирующее множество.
            if (set2._items != null && set2._items.Count > 0)
            {
                // т.к. список является ссылочным типом, 
                // то необходимо не просто передавать данные, а создавать их дубликаты.
                items.AddRange(new List<T>(set2._items));
            }

            // Удаляем все дубликаты из результирующего множества элементов данных.
            resultSet._items = items.Distinct().ToList();

            // Возвращаем результирующее множество.
            return resultSet;
        }

        /// <summary>
        /// Пересечение множеств.
        /// </summary>
        /// <param name="set1"> Первое множество. </param>
        /// <param name="set2"> Второе множество. </param>
        /// <returns> Новое множество, содержащее совпадающие элементы данных из полученных множеств. </returns>
        public static Set<T> Intersection(Set<T> set1, Set<T> set2)
        {
            // Проверяем входные данные на пустоту.
            if (set1 == null)
            {
                throw new ArgumentNullException(nameof(set1));
            }

            if (set2 == null)
            {
                throw new ArgumentNullException(nameof(set2));
            }

            // Результирующее множество.
            var resultSet = new Set<T>();

            // Выбираем множество содержащее наименьшее количество элементов.
            if (set1.Count < set2.Count)
            {
                // Первое множество меньше.
                // Проверяем все элементы выбранного множества.
                foreach (var item in set1._items)
                {
                    // Если элемент из первого множества содержится во втором множестве,
                    // то добавляем его в результирующее множество.
                    if (set2._items.Contains(item))
                    {
                        resultSet.Add(item);
                    }
                }
            }
            else
            {
                // Второе множество меньше или множества равны.
                // Проверяем все элементы выбранного множества.
                foreach (var item in set2._items)
                {
                    // Если элемент из второго множества содержится в первом множестве,
                    // то добавляем его в результирующее множество.
                    if (set1._items.Contains(item))
                    {
                        resultSet.Add(item);
                    }
                }
            }

            // Возвращаем результирующее множество.
            return resultSet;
        }

        /// <summary>
        /// Разность множеств.
        /// </summary>
        /// <param name="set1"> Первое множество. </param>
        /// <param name="set2"> Второе множество. </param>
        /// <returns> Новое множество, содержащее не совпадающие элементы данных между полученными множествами. </returns>
        public static Set<T> Difference(Set<T> set1, Set<T> set2)
        {
            // Проверяем входные данные на пустоту.
            if (set1 == null)
            {
                throw new ArgumentNullException(nameof(set1));
            }

            if (set2 == null)
            {
                throw new ArgumentNullException(nameof(set2));
            }

            // Результирующее множество.
            var resultSet = new Set<T>();

            // Проходим по всем элементам первого множества.
            foreach (var item in set1._items)
            {
                // Если элемент из первого множества не содержится во втором множестве,
                // то добавляем его в результирующее множество.
                if (!set2._items.Contains(item))
                {
                    resultSet.Add(item);
                }
            }

            // Проходим по всем элементам второго множества.
            foreach (var item in set2._items)
            {
                // Если элемент из второго множества не содержится в первом множестве,
                // то добавляем его в результирующее множество.
                if (!set1._items.Contains(item))
                {
                    resultSet.Add(item);
                }
            }

            // Удаляем все дубликаты из результирующего множества элементов данных.
            resultSet._items = resultSet._items.Distinct().ToList();

            // Возвращаем результирующее множество.
            return resultSet;
        }

        /// <summary>
        /// Подмножество.
        /// </summary>
        /// <param name="set1"> Множество, проверяемое на вхождение в другое множество. </param>
        /// <param name="set2"> Множество в которое проверяется вхождение другого множества. </param>
        /// <returns> Является ли первое множество подмножеством второго. true - является, false - не является. </returns>
        public static bool Subset(Set<T> set1, Set<T> set2)
        {
            // Проверяем входные данные на пустоту.
            if (set1 == null)
            {
                throw new ArgumentNullException(nameof(set1));
            }

            if (set2 == null)
            {
                throw new ArgumentNullException(nameof(set2));
            }

            // Перебираем элементы первого множества.
            // Если все элементы первого множества содержатся во втором,
            // то это подмножество. Возвращаем истину, иначе ложь.
            var result = set1._items.All(s => set2._items.Contains(s));
            return result;
        }

        /// <summary>
        /// Вернуть перечислитель, выполняющий перебор всех элементов множества.
        /// </summary>
        /// <returns> Перечислитель, который можно использовать для итерации по коллекции. </returns>
        public IEnumerator<T> GetEnumerator()
        {
            // Используем перечислитель списка элементов данных множества.
            return _items.GetEnumerator();
        }

        /// <summary>
        /// Вернуть перечислитель, который осуществляет итерационный переход по множеству.
        /// </summary>
        /// <returns> Объект IEnumerator, который используется для прохода по коллекции. </returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            // Используем перечислитель списка элементов данных множества.
            return _items.GetEnumerator();
        }
    }
}

Вызов

using System;

namespace Set
{
    class Program
    {
        static void Main(string[] args)
        {
            // Создаем множества.
            var set1 = new Set<int>()
            {
                1, 2, 3, 4, 5, 6
            };

            var set2 = new Set<int>()
            {
                4, 5, 6, 7, 8, 9
            };

            var set3 = new Set<int>()
            {
                2, 3, 4
            };

            // Выполняем операции со множествами.
            var union = Set<int>.Union(set1, set2);
            var difference = Set<int>.Difference(set1, set2);
            var intersection = Set<int>.Intersection(set1, set2);
            var subset1 = Set<int>.Subset(set3, set1);
            var subset2 = Set<int>.Subset(set3, set2);

            // Выводим исходные множества на консоль.
            PrintSet(set1, "Первое множество: ");
            PrintSet(set2, "Второе множество: ");
            PrintSet(set3, "Третье множество: ");

            // Выводим результирующие множества на консоль.
            PrintSet(union, "Объединение первого и второго множества: ");
            PrintSet(difference, "Разность первого и второго множества: ");
            PrintSet(intersection, "Пересечение первого и второго множества: ");
            
            // Выводим результаты проверки на подмножества.
            if(subset1)
            {
                Console.WriteLine("Третье множество является подмножеством первого.");
            }
            else
            {
                Console.WriteLine("Третье множество не является подмножеством первого.");
            }

            if (subset2)
            {
                Console.WriteLine("Третье множество является подмножеством второго.");
            }
            else
            {
                Console.WriteLine("Третье множество не является подмножеством второго.");
            }

            Console.ReadLine();
        }

        /// <summary>
        /// Вывод множества на консоль.
        /// </summary>
        /// <param name="set"> Множество. </param>
        /// <param name="title"> Заголовок перед выводом множества. </param>
        private static void PrintSet(Set<int> set, string title)
        {
            Console.Write(title);
            foreach (var item in set)
            {
                Console.Write($"{item} ");
            }
            Console.WriteLine();
        }
    }
}

Заключение

На платформе .NET все операции над множествами уже оптимально реализованы в рамках LINQ запросов, поэтому реализовывать самостоятельно нет необходимости. Исходный код доступен в репозитории github https://github.com/shwanoff/Set.

 
×
%d такие блоггеры, как: