Перегляд вихідного коду сторінки Множина (тип даних)

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

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

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

== Теорія типів ==
В [[Теорія типів|теорії типів]] множини, в основному, ототожнюються з [[Характеристична функція|індикаторною функцією]] (характеристичною функцією): таким чином, множина значень типу <math>A</math>  може бути позначена <math>2^A</math> або <math>P(A)</math>. (Підтипи або підмножини можуть бути змодельовані уточнювальними типами, а [[Клас еквівалентності|фактор-множини]] замінені {{Нп|Сетоїд|сетоїдами||Setoid}}.) Характеристична функція <math>F</math> множини <math>S</math> визначається так:

<math>F(x) = \begin{cases}1, & \text{if }x \in\text{ S} \\ 0, & \text{if }x\not\in\text{ S} \end{cases}</math>

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

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

''Визначають такі операції алгебри множин:'' 
* <code>union(''S,T'')</code>: повертає об’єднання множин S і T.
* <code>intersection(''S,T'')</code>: повертає перетин множин S і T.
* <code>difference(''S,T'')</code>: повертає різницю множин S і T.
* <code>subset(''S,T'')</code>: предикат, що перевіряє чи є множина S підмножиною множини T. 

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

''Типові операції, які задаються статичною структурою множини S:'' 
* <code>is_element_of(''x,S'')</code>: перевіряє входження значення X у множину S.
* <code>is_empty(''S'')</code>: перевіряє чи є множина S порожньою.
* <code>size(''S'')</code> або <code>cardinality(''S'')</code>: повертає число елементів S множини. 
* <code>iterate(''S'')</code>: функція, що повертає один довільно вибраний елемент множини S при кожному виклику.
* <code>enumerate(''S'')</code>: повертає у довільному порядку список елементів, які містяться у множини S.
* <code>build(<math>x_1, x_2,...,x_n</math>)</code>: створює множину зі значеннями <math>x_1,x_2,...,x_n</math>.
* create_from(''collection''): створює нову множину, яка містить у собі всі елементи даної сукупності або всі елементи, повернуті ітератором.

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

''Динамічні структури зазвичай додають:'' 
* <code>create()</code>: створює нову, спочатку порожню множину.
* <code>create_with_capacity(n)</code>: створює нову, спочатку порожню множину, але розмірністю n. 
* <code>add(x,S)</code>: додає елемент x до множини S, якщо такого ще не існує
* <code>remove(S,x)</code>: видаляє елемент x із множини S, якщо існує.
* <code>capacity(S)</code>: повертає максимальне число елементів, яке може містити S.
Деякі множинні структури можуть дозволити собі використовувати лише деякі із цих операцій.  Потреба кожної операції буде залежати від реалізації, а також конкретних значень, що входять до множини, і порядку, у якому вони розташовані у множині. 

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

''Існує багато інших операцій, що можуть бути визначені щодо термінів вище, такі як:''
* <code>pop(S)</code>: повертає довільно вибраний елемент множини S, і видаляє його з S.
* <code>pick(S)</code>: повертає довільно вибраний елемент множини S. З функціональної точки зору мутатор <code>рор</code> може бути інтерпретований як пара селекторів <code>(pick, rest)</code> де <code>rest</code> повертає множину, що включає в себе усі елементи, окрім вибраного.
* <code>map(F,S)</code>: повертає множину різних значень, отриманих від F до кожного елемента S.
* <code>filter(P,S)</code>: повертає підмножину елементів, що містяться у S, та задовольняють даний предикат P.
* <code>fold(A<math>_0</math>,F,S)</code>: повертає значення A, після застосування формули <code><math>A_{i+1}:=F(A_i,e)</math></code> для кожного елемента e у S, для деякої бінарної операції F. F повинна бути асоціативною і комунікативною, для того, щоб бути чітко визначеною. 
* <code>clear(S)</code>: видаляє усі елементи S.
* <code>equal(S<math>_1</math>, S<math>_2</math>)</code>: перевіряє чи є дві множини рівними (тобто мають усі однакові елементи).
* hash(S): повертає хеш-значення для статичної множини S, таке, якщо <code>equal(S<math>_1</math>,S<math>_2</math>)</code> тоді <code>hash(S<math>_1</math>) = hash(S<math>_2</math>)</code>.
''Операції для множин, що містять елементи спеціального типу:''
* <code>sum(S)</code>: повертає суму усіх елементів множини S, для деякого визначення суми. Наприклад, сума для цілих або дійсних чисел може бути визначена так: <code>fold(0, add, S)</code>.
* <code>collapse(S)</code>: дано множину множин, повертає об’єднання ряду множин. Наприклад, <code>collapse(<nowiki>{{1}, {2, 3}}</nowiki>) == {1, 2, 3}</code> може розглядатись як сума.
* <code>flatten(S)</code>: дано множину, що складається із множин і атомних елементів (елементи, що не є множиною), повертає множину, елементи якої є початковою множиною верхнього рівня або елементи множини, які входять до цієї множини. Іншими словами, видаляє рівень вкладеності, такий як: collapse але дозволяє атоми. Це може бути зроблено один раз або декілька разів, для того, щоб отримати множину тільки атомних елементів. Наприклад, <code>flatten({1, {2, 3}}) == {1, 2, 3}</code>.
* <code>nearest(S,x)</code>: повертає елемент множини S, що є найближчим до значення x.
* <code>min(S)</code>, <code>max(S)</code>: повертає мінімальний/максимальний елементи множини S.

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

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

Крім того, у мовах, які підтримують карти, а не множини, множини можуть бути реалізовані на основі карти. Наприклад, загальна ідіома у мові програмування Perl, що конвертує масив у хеш, чиї параметри приймають параметри контрольного елемента, для використання як масиву: <syntaxhighlight>
my %elements = map { $_ => 1 } @elements;
</syntaxhighlight>

'''Множина в [[Мова програмування Pascal|Паскалі]]'''

У мові [[Мова програмування Pascal|Паскаль]] [[множина]]&nbsp;— складовий [[тип даних]], який зберігає інформацію про присутність у множині об'єктів будь-якого рахункового типу. Потужність цього типу визначає розмір множини&nbsp;— 1 [[біт]] на елемент. У [[Turbo Pascal]] є обмеження на 256 елементів, у деяких інших реалізаціях це обмеження ослаблене. Приклад роботи з множинами:<syntaxhighlight lang="pascal">
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.
</syntaxhighlight>

== Мультимножина ==
{{main|Мультимножина}}

Узагальненням поняття множини є '''[[мультимножина]]''' чи  '''сумка''' ({{lang-en|bag}}), яка подібна на множину, але дозволяє дублікати (повторення однакових значень).

== Джерела ==
* {{CLRS|chapter=10. Елементарні структури даних}}

{{Datastructure-stub}}
{{Структури даних}}
{{Типи даних}}

[[Категорія:Типи даних]]
[[Категорія:Структури даних]]
[[Категорія:Складені типи даних]]
[[Категорія:Статті з прикладами коду мовою Pascal]]