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


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

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *