Множества и отношения

Множество — это коллекция уникальных элементов, в которой важен факт наличия, но не порядок.

Множество по определению:

не содержит дубликатов
порядок не имеет значения {1, 2, 3} и {3, 1, 2} — одно и то же множество.
отвечает только на вопрос: "принадлежит — не принадлежит"

1. Принадлежность и Подмножество

Принадлежность (x ∈ A) - элемент x принадлежит множеству A, если x находится внутри набора A.

use std::collections::HashSet;
fn main(){
    // let allowed: HashSet<_> = ["gmail.com", "yandex.ru"].into_iter().collect();
    let allowed = HashSet::from(["gmail.com", "yandex.ru"]);
    let domain = "gmail.com";

    if allowed.contains(domain) {
        println!("(domain ∈ allowed) - элемент domain принадлежит множеству allowed");
    }
    // Почему не массивы? Потому что в массиве → дубликаты возможны и алгоритм нахождения дольше
 
}

Подмножество A ⊆ B - множество A является подмножеством B, если каждый элемент A содержится в B.

Т.е. все элементы A входят в B. Это проверка “достаточности”.

Для множества элементов S = [A, B, C]

Количество подмножеств всегда равно 2ⁿ (n = количество элементов)

Для каждого элемента есть два варианта: включить или не включить, поэтому мы умножаем двойку саму на себя n раз

Для нашего множества из трех вариантов количество подмножеств будет 2³:

Общее количество подмножеств = 2 × 2 × 2 = 8 = 2³

[]      -> 000
[A]     -> 001
[B]     -> 010
[A,B]   -> 011
[C]     -> 100
[A,C]   -> 101
[B,C]   -> 110
[A,B,C] -> 111

use std::collections::HashSet;
fn main(){
    // Пользователь пытается выполнить действие, требующее набора прав:
    let required = HashSet::from(["read", "write"]);
    let user = HashSet::from(["read", "write", "delete"]);

    if user.is_superset(&required) {
        println!("(required ⊆ user)");// множество `required` является подмножеством `user`, 
        // т.е. все требования required содержатся в наборе user
    }
}

2. Операции над множествами

Пересечение (intersection) (A ∩ B) - элементы, которые есть и в A, и в B. Нахождение общего.

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
    
    for x in &intersection {
        println!("{}", x); // 7, 3
    }

    Ok(())
}

Объединение (union) (A ∪ B) - элементы, которые есть либо в A, либо в B (дубликатов нет).

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    let union: HashSet<_> = a.union(&b).cloned().collect();
 
    for x in &union {
        println!("{}", x); // 7, 3, 4, 1
    }

    Ok(())
}

Разность (A \ B) - элементы, которые есть в A, но НЕ в B.

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    // `(A \ B)` - элементы, которые есть в `A`, но НЕ в `B`
    let diff: HashSet<_> = a.difference(&b).cloned().collect();
 
    for x in &diff {
        println!("{}", x); // 1
    }

    // `(B \ A)` - элементы, которые есть в `B`, но НЕ в `A`
    let diff: HashSet<_> = b.difference(&a).cloned().collect();
 
    for x in &diff {
        println!("{}", x); // 4
    }

    Ok(())
}

Симметрическая разность (xor) (A △ B) - элементы, которые есть либо только в A, либо только в B, но не в обоих.

Это объединение минус пересечение: (A ∪ B) \ (A ∩ B)

Например: какие настройки изменились между конфигурациями

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let user_state_1 = HashSet::from(["read", "write", "check" ]);
    let user_state_2 = HashSet::from(["read", "write", "delete"]);
    
    let sym: HashSet<_> = user_state_1.symmetric_difference(&user_state_2).cloned().collect();
 
    for x in &sym {
        println!("{}", x); // delete, check
    }
    
    // Или
    let union: HashSet<_> = user_state_1.union(&user_state_2).cloned().collect();
    let intersection: HashSet<_> = user_state_1.intersection(&user_state_2).cloned().collect();
    let sym: HashSet<_> = union.difference(&intersection).cloned().collect();
    
    for x in &sym {
        println!("{}", x); // delete, check
    }
 
    Ok(())
}

3. Декартово произведение множеств

(ключ к JOIN, графам, отношениям, БД, моделям состояний)

A × B - взять каждый элемент A и скрестить со всеми B

A = {1, 2}
B = {x, y}

A × B = {(1, x), (1, y), (2, x), (2, y)}

fn main() -> std::io::Result<()> {
    
    let A = ["1","2"];
    let B = ["x","y"];
    
    for a in &A {
        for b in &B {
            print!("({a}, {b}) ");// (1, x) (1, y) (2, x) (2, y)
        }
    }
 
    Ok(())
}

SQL JOIN — это декартово произведение + фильтр:

SELECT * FROM A JOIN B ON cond

берёт все пары строк таблиц
оставляет только те, что удовлетворяют условию

А join — операция над отношениями.

inner join — пересечение
left join — проекция + фильтр
cartesian join — полное декартово произведение

Графы полностью определяются как декартово произведение

Граф = (V, E):

V — множество вершин
E — множество ребер

Ребро — это пара вершин: (u, v)

То есть E является подмножеством декартова произведения: E ⊆ V × V

Все алгоритмы графов опираются на это определение:

поиск смежных вершин
матрица смежности
представление ребер
поиск путей

Отношения в БД — это подмножество декартова произведения доменов

Любая таблица в базе — это множество кортежей, а каждый кортеж — элемент декартова произведения доменов столбцов.

Например таблица: (id: int, name: varchar) формально — подмножество: Int × String. Это фундамент реляционной модели.

Пример:

Не нормализованная таблица:

Orders(id, user_name, user_email, product_name, product_price)

Нормализация — это про преобразование отношений, чтобы убрать:

дублирование данных: user и product fields дублируются для каждого заказа
аномалии вставки: невозможно добавить пользователя без заказа
аномалии обновления: изменение email требует изменения многих других строк Orders с этим пользователем
аномалии удаления: удаление последнего заказа удалит и пользователя, как будто его и небыло в системе

Нормализация = разбивание на подмножества отношения:

Users(id, name, email)
Products(id, name, price)
Orders(id, user_id, product_id)

Машины состояний

Если у вас есть:

множество состояний
множество входов

То переходы = декартово произведение: State × Input → State (то есть каждая комбинация вход + состояние — отдельный случай)

Используется при проектировании API FSM (Finite State Machine)

FSM (Конечный автомат) — это математическая модель вычислений, используемая для проектирования логики систем. Она представляет собой абстракцию, которая в любой момент времени может находиться только в одном из конечного числа состояний.

Простыми словами, представьте себе дверь:

Состояния: Закрыта, Открыта, Заблокирована.
События (Переходы): Повернуть ключ, Потянуть ручку, Нажать на замок.

Вы не можете перейти из состояния Закрыта в состояние Заблокирована, не выполнив событие Повернуть ключ. Логика всех возможных переходов между состояниями и есть FSM.

Разработка API FSM — это процесс проектирования и создания API, которое управляет состоянием какого-либо объекта или процесса, строго следуя правилам, определенным в конечном автомате (FSM).

4. Отношения и функции как множества

Если понять его правильно — становится яснее всё: типы данных, функции, API-контракты, БД, графы, отображения, enum-ы, даже ошибки типов.

Отношение = подмножество декартова произведения.

Почему именно подмножество? Потому что если бы было множество то это означало бы результат обычного декартового произведения, а подмножество означает что мы выбрали часть из декартового произведение множеств т.е. оно входит в него.

A = {1, 2}
B = {x, y}

# `A × B` это декартово произведение т.е. все возможные пары
A × B = {(1, x), (1, y), (2, x), (2, y)}

# `R ⊆ A × B` а это отношение R = выбранные пары, которые реально связаны между собой в нашей задаче
`R ⊆ A × B` = {(1, x)} # т.е. только одна пара нас интересует и она является отношением

# две пары нас интересует и они тоже является отношением 
`R ⊆ A × B` = {(1, x), (2, x)} 

# идентично декартовому произведение но и это является отношением тоже
`R ⊆ A × B` = {(1, x), (1, y), (2, x), (2, y)}

Функция f ⊆ A × B - для каждого a ∈ A существует ровно один b ∈ B, что (a, b) ∈ f.

Короче, функция имеет только один вариант соответсвия из множества A к варианту из множества B, поэтому и называется подмножество, в отличии от полного множества всех пересечений - декартовое произведение, где для каждого варианта из A соответвует один вариант B

Каждый элемент домена должен иметь ровно один выход. Если элемент домена имеет два или более выходов — это критическая ошибка, это — отношение.

Это особый вид отношения:

каждый элемент домена имеет ровно один образ
нет неоднозначности

Функция — это отношение между двумя множествами, которое каждому элементу первого множества (домена) ставит в соответствие ровно один элемент второго множества (кодомена).

Домeн = множество допустимых входов
Кодомен = множество возможных выходов
Ровно один выход на каждый вход = главное свойство функции

Декартово произведение `A × B`:   Функция `f ⊆ A × B`:
A1 → B1,B2,B3                     A1 → B2 т.е. только один вариант, но может быть и другой, главное что бы было соответсвие со входом, постоянно один и тот же
A2 → B1,B2,B3                     A2 → B1
A3 → B1,B2,B3                     A3 → B3

Для понимания как строить функции в плане программирования, которые не ломаются на неожиданных входах.

/*
Каждому элементу домена соответствует ровно один элемент кодомена

f ⊆ Domen × i32
f = {
    (One, 1),
    (Two, 2),
    (Three, 3)
}

Кодомен — это “множество, в которое функция мапит элементы домена”
Подмножество (range) — это то, что реально используется


Тип кодомена = i32 → это множество всех возможных значений i32
Codomain(f) = i32 = {...,-2_147_483_648, ..., 2_147_483_647}

Но внутри функции мы возвращаем только 1, 2 или 3
Фактические значения функции = range(f) = {1,2,3}
Это называется образ функции или range

Реальные значения функции могут быть меньше кодомена, это нормально

Декартово произведение было бы: все возможные пары (Domen × range(f)) → 9 пар
Функция выбирает ровно одну пару для каждого элемента домена → 3 пары
*/
enum Domen {
    One=1,
    Two,
    Three
}

// Тип безопасная функция
fn function(d: Domen)-> i32{
    return match d{
        Domen::One => 1,
        Domen::Two => 2,
        Domen::Three => 3,
    }
}
// или
//fn function(d: Domen)-> i32{ d as i32}

// Частичная функция может быть вызвана для любого элемента домена, но не гарантирует реального i32 значения
fn partial_function(d: Domen)-> Option<i32>{
    return match d{
        Domen::One => Some(1),
        Domen::Two => Some(2),
        Domen::Three => None,
        _ => None,
    }
}

// Кодомен меньше домена → неинъективная функция, но тип безопасна
fn non_injective_function(d: Domen) -> bool {
    match d {
        Domen::One => true,
        Domen::Two => false,
        Domen::Three => false,
    }
}

fn main() -> std::io::Result<()> {
     
    let kodomen = function(Domen::Three);
    print!("{kodomen}");// 3
 
    Ok(())
}

Частичная функция. Функция может быть не определена для некоторых элементов домена.

Частичные функции появляются, когда:

Не обрабатывается какой-то вариант из домена
Функция может “не вернуть значение” → тогда используют Option или Result

Когда отношение не является функцией (например, пользователь может иметь несколько ролей → не функция, а отношение).

Функция = детерминированный переход состояния:

Каждый входной набор → ровно одно следующее состояние → функция
Если не определено → частичная функция → нужна обработка ошибок / Option

Биекция (Bijective)

Полное, взаимно-однозначное соответствие.

Функция биективна, если она одновременно:

инъективна (Injective) (один-к-одному) - разные элементы домена → всегда разные элементы кодомена, никакие два входа не дают один и тот же выход.
сюръективна (Surjective) (покрывает весь кодомен) - каждый элемент кодомена кто-то получает из домена, т.е. весь кодомен покрыт.

Практическое значение: Реализация кодировок (если кодировка НЕ биективна — обратное преобразование невозможно)

enum ↔ integer representation
UTF-8 ↔ Unicode Scalar
base64 ↔ bytes

Практическое значение: Сериализация / десериализация

serde - struct ↔ JSON

5. Мощность (размер множества)

Мощность множества = количество элементов в множестве.

Это лежит в основе:

сложности алгоритмов
количества состояний программы
количества возможных комбинаций входов
вероятностей
размеров enum
теории типов
безопасности (proof of correctness)

Примеры:

HashSet / HashMap

Операции:

insert, lookup, delete = O(1) зависят от мощности множества ключей

Потому что вычисляется вероятность коллизий, а она зависит от: |keys| vs |hash_space|

То есть мощность множества ключей напрямую влияет на сложность
Сортировка

оличество перестановок множества размером n: N log N — оптимальная сортировка
Полный перебор (exhaustive search)
Вот почему вложенные циклы = квадратичная/кубическая сложность.
```
|A| = n  
|A × A| = n²  
|A × A × A| = n³
```

Мощность как количество возможных состояний программы

enum Color { Red, Green, Blue }

Мощность: |Color| = 3

Мощность: Option<bool> = 3

fn f(c: Color, flag: Option<bool>)

То количество комбинаций входов:

|Color × Option<Bool>| = 3 * 3 = 9 состояний