Множина (тип даних)

Множина — абстрактний тип даних і структура даних в інформатиці, є реалізацією математичного об'єкта скінченна множина.

Дані типу «множина» дозволяють зберігати обмежене число значень певного типу без певного порядку. Повторення значень, як правило, неприпустимо. За винятком того, що множина в програмуванні скінченне, воно загалом відповідає концепції математичної множини. Для цього типу в мовах програмування зазвичай передбачені стандартні операції над множинами.

Залежно від ідеології, різні мови програмування розглядають множину як простий чи складний тип даних.

Теорія типів

В теорії типів множини, в основному, ототожнюються з індикаторною функцією (характеристичною функцією): таким чином, множина значень типу ${\displaystyle A}$  може бути позначена ${\displaystyle 2^{A}}$ або ${\displaystyle P(A)}$. (Підтипи або підмножини можуть бути змодельовані уточнювальними типами, а фактор-множини замінені ^[en].) Характеристична функція ${\displaystyle F}$ множини ${\displaystyle S}$ визначається так:

${\displaystyle F(x)={\begin{cases}1,&{\text{if }}x\in {\text{ S}}\\0,&{\text{if }}x\not \in {\text{ S}}\end{cases}}}$

Теоретично, велика кількість інших абстрактних структур даних може розглядатись як множина з додатковими операціями і/або додатковими аксіомами, накладеними на стандартні операції. Наприклад, абстрактна структура даних купа розглядається як множина структур із min(S) операцією, яка повертає найменший елемент.

Операції

Основні теоретико-множинні операції

Визначають такі операції алгебри множин: 

• union(S,T): повертає об’єднання множин S і T.
• intersection(S,T): повертає перетин множин S і T.
• difference(S,T): повертає різницю множин S і T.
• subset(S,T): предикат, що перевіряє чи є множина S підмножиною множини T. 

Статичні множини

Типові операції, які задаються статичною структурою множини S: 

• is_element_of(x,S): перевіряє входження значення X у множину S.
• is_empty(S): перевіряє чи є множина S порожньою.
• size(S) або cardinality(S): повертає число елементів S множини. 
• iterate(S): функція, що повертає один довільно вибраний елемент множини S при кожному виклику.
• enumerate(S): повертає у довільному порядку список елементів, які містяться у множини S.
• build(${\displaystyle x_{1},x_{2},...,x_{n}}$): створює множину зі значеннями ${\displaystyle x_{1},x_{2},...,x_{n}}$.
• create_from(collection): створює нову множину, яка містить у собі всі елементи даної сукупності або всі елементи, повернуті ітератором.

Динамічні множини

Динамічні структури зазвичай додають: 

• create(): створює нову, спочатку порожню множину.
• create_with_capacity(n): створює нову, спочатку порожню множину, але розмірністю n. 
• add(x,S): додає елемент x до множини S, якщо такого ще не існує
• remove(S,x): видаляє елемент x із множини S, якщо існує.
• capacity(S): повертає максимальне число елементів, яке може містити S.

Деякі множинні структури можуть дозволити собі використовувати лише деякі із цих операцій.  Потреба кожної операції буде залежати від реалізації, а також конкретних значень, що входять до множини, і порядку, у якому вони розташовані у множині. 

Додаткові операції

Існує багато інших операцій, що можуть бути визначені щодо термінів вище, такі як:

• pop(S): повертає довільно вибраний елемент множини S, і видаляє його з S.
• pick(S): повертає довільно вибраний елемент множини S. З функціональної точки зору мутатор рор може бути інтерпретований як пара селекторів (pick, rest) де rest повертає множину, що включає в себе усі елементи, окрім вибраного.
• map(F,S): повертає множину різних значень, отриманих від F до кожного елемента S.
• filter(P,S): повертає підмножину елементів, що містяться у S, та задовольняють даний предикат P.
• fold(A${\displaystyle _{0}}$,F,S): повертає значення A, після застосування формули ${\displaystyle A_{i+1}:=F(A_{i},e)}$ для кожного елемента e у S, для деякої бінарної операції F. F повинна бути асоціативною і комунікативною, для того, щоб бути чітко визначеною. 
• clear(S): видаляє усі елементи S.
• equal(S${\displaystyle _{1}}$, S${\displaystyle _{2}}$): перевіряє чи є дві множини рівними (тобто мають усі однакові елементи).
• hash(S): повертає хеш-значення для статичної множини S, таке, якщо equal(S${\displaystyle _{1}}$,S${\displaystyle _{2}}$) тоді hash(S${\displaystyle _{1}}$) = hash(S${\displaystyle _{2}}$).

Операції для множин, що містять елементи спеціального типу:

• sum(S): повертає суму усіх елементів множини S, для деякого визначення суми. Наприклад, сума для цілих або дійсних чисел може бути визначена так: fold(0, add, S).
• collapse(S): дано множину множин, повертає об’єднання ряду множин. Наприклад, collapse({{1}, {2, 3}}) == {1, 2, 3} може розглядатись як сума.
• flatten(S): дано множину, що складається із множин і атомних елементів (елементи, що не є множиною), повертає множину, елементи якої є початковою множиною верхнього рівня або елементи множини, які входять до цієї множини. Іншими словами, видаляє рівень вкладеності, такий як: collapse але дозволяє атоми. Це може бути зроблено один раз або декілька разів, для того, щоб отримати множину тільки атомних елементів. Наприклад, flatten({1, {2, 3}}) == {1, 2, 3}.
• nearest(S,x): повертає елемент множини S, що є найближчим до значення x.
• min(S), max(S): повертає мінімальний/максимальний елементи множини S.

 Реалізація

Множини можна реалізувати, використовуючи різні структури даних, які забезпечують різні часові затрати і просторові компроміси для різних операцій. Деякі реалізації створені для того, щоб покращити ефективність дуже спеціалізованих операцій, таких як: nearest або union. Реалізації описані для «загального використання», як правило, прагнуть оптимізувати element_of, add та delete операції. Простою реалізацією є використання списку (абстрактний тип даних), ігноруючи порядок елементів та уникаючи їх повтору. Це просто, але неефективно, бо операції на перевірку належності у множині чи видалення елементу O(n) повинні сканувати увесь список. Замість цього, множини часто реалізуються з використанням більш ефективних структур даних, а саме, різних видів дерев, префіксних дерев або хеш-таблиць.

Так як множини можна інтерпретувати як щось на зразок карти (індикаторною функцією), вони зазвичай реалізуються у той самий спосіб, що і (часткові) карти (асоціативні масиви) – у цьому разі значення кожної пари ключа-значення має тип одиниці або контрольного елемента (наприклад, 1), а саме збалансоване дерево для відсортованого масиву (O(log n) для більшості операцій) або хеш-таблицю для невідсортованого масиву (O(1) в середньому випадку, але O(n) в найгіршому випадку, для більшості операцій). Відсортована лінійна хеш-таблиця може бути використана для забезпечення детерміновано впорядкованих множин.

Крім того, у мовах, які підтримують карти, а не множини, множини можуть бути реалізовані на основі карти. Наприклад, загальна ідіома у мові програмування Perl, що конвертує масив у хеш, чиї параметри приймають параметри контрольного елемента, для використання як масиву: 

my %elements = map { $_ => 1 } @elements;

Множина в Паскалі

У мові Паскаль множина — складовий тип даних, який зберігає інформацію про присутність у множині об'єктів будь-якого рахункового типу. Потужність цього типу визначає розмір множини — 1 біт на елемент. У Turbo Pascal є обмеження на 256 елементів, у деяких інших реалізаціях це обмеження ослаблене. Приклад роботи з множинами:

type  {визначаємо базові для множин зліченний тип і тип-діапазон}  colors = (red,green,blue);  smallnumbers = 0..10;  {визначаємо множини з наших типів}  colorset = set of colors;  numberset = set of smallnumbers;  {можна і не задавати тип окремо}  anothernumberset = set of 0..20; {оголошуємо змінні типу множин} var  nset1,nset2,nset3:numberset;  cset:colorset; begin  nset1 := [0,2,4,6,8,10]; {задаємо у вигляді конструктора множини}  cset := [red,blue]; {простим перерахуванням елементів}  nset2 := [1,3,9,7,5]; {порядок перерахування не важливий}  nset3 := []; {пуста множина}  include(nset3,7); {додавання елемента}  exclude(nset3,7); {вилучення елемента}  nset1 := [0..5]; {можливо задавати елементи діапазоном}  nset3 := nset1 + nset2; {об'єднання}  nset3 := nset1 * nset2; {перетин}  nset3 := nset1 - nset2; {різниця}  if (5 in nset2) or {перевірка на входження елемента}  (green in cset) then  {…} end. 

Мультимножина

Докладніше: Мультимножина

Узагальненням поняття множини є мультимножина чи сумка (англ. bag), яка подібна на множину, але дозволяє дублікати (повторення однакових значень).

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .