Алгоритми і структури даних для початківців: множини

Множина – це колекція, яка реалізує основні математичні операції над множинами: перетини (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”}