Какие знаешь операции в множестве?

Операции в множествах (Set Operations)

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

Основные операции

# Создание множества
set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7, 8}

print(f"set1: {set1}")
print(f"set2: {set2}")

1. Объединение (Union)

Объединение — все элементы из обоих множеств (без дубликатов).

# Вариант 1: оператор |
result = set1 | set2
print(result)  # {1, 2, 3, 4, 5, 6, 7, 8}

# Вариант 2: метод union()
result = set1.union(set2)
print(result)  # {1, 2, 3, 4, 5, 6, 7, 8}

# Вариант 3: множественное объединение
set3 = {9, 10}
result = set1 | set2 | set3
print(result)  # {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

# Сложность: O(len(set1) + len(set2))

2. Пересечение (Intersection)

Пересечение — элементы, которые есть в обоих множествах.

# Вариант 1: оператор &
result = set1 & set2
print(result)  # {4, 5}

# Вариант 2: метод intersection()
result = set1.intersection(set2)
print(result)  # {4, 5}

# Вариант 3: множественное пересечение
set3 = {4, 5, 9}
result = set1 & set2 & set3
print(result)  # {4, 5}

# Использование: найти общих подписчиков
followers_alice = {"bob", "charlie", "diana"}
followers_bob = {"alice", "charlie", "evan"}
common_followers = followers_alice & followers_bob
print(common_followers)  # {'charlie'}

3. Разность (Difference)

Разность — элементы, которые есть в первом множестве, но нет во втором.

# Вариант 1: оператор -
result = set1 - set2
print(result)  # {1, 2, 3}

# Вариант 2: метод difference()
result = set1.difference(set2)
print(result)  # {1, 2, 3}

# Разность не коммутативна
print(set2 - set1)  # {6, 7, 8}

# Использование: найти пользователей, кто подписан на A, но не на B
following_user1 = {"alice", "bob", "charlie"}
following_user2 = {"bob", "diana"}
unique_to_user1 = following_user1 - following_user2
print(unique_to_user1)  # {'alice', 'charlie'}

4. Симметричная разность (Symmetric Difference)

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

# Вариант 1: оператор ^
result = set1 ^ set2
print(result)  # {1, 2, 3, 6, 7, 8}

# Вариант 2: метод symmetric_difference()
result = set1.symmetric_difference(set2)
print(result)  # {1, 2, 3, 6, 7, 8}

# Это то же самое, что (A - B) | (B - A)
result = (set1 - set2) | (set2 - set1)
print(result)  # {1, 2, 3, 6, 7, 8}

# Использование: найти различия между двумя версиями документа
old_tags = {"python", "django", "rest", "api"}
new_tags = {"python", "fastapi", "async", "api"}
changed_tags = old_tags ^ new_tags
print(changed_tags)  # {'django', 'rest', 'fastapi', 'async'}

5. Проверка подмножества (Subset)

Подмножество — все элементы A содержатся в B.

small_set = {1, 2}
large_set = {1, 2, 3, 4, 5}

# Вариант 1: оператор <=
result = small_set <= large_set
print(result)  # True

# Вариант 2: метод issubset()
result = small_set.issubset(large_set)
print(result)  # True

# Строгое подмножество (<)
result = small_set < large_set
print(result)  # True (и не равны)

# Проверка равенства подмножеств
set_a = {1, 2}
set_b = {1, 2}
result = set_a <= set_b and set_b <= set_a
print(result)  # True (это эквивалент ==)

# Использование: проверить, покрыли ли мы все требования
required_features = {"auth", "api", "database"}
implemented_features = {"auth", "api", "database", "cache", "logging"}
all_required_done = required_features <= implemented_features
print(all_required_done)  # True

6. Проверка надмножества (Superset)

Надмножество — B содержит все элементы A.

large_set = {1, 2, 3, 4, 5}
small_set = {1, 2}

# Вариант 1: оператор >=
result = large_set >= small_set
print(result)  # True

# Вариант 2: метод issuperset()
result = large_set.issuperset(small_set)
print(result)  # True

# Строгое надмножество (>)
result = large_set > small_set
print(result)  # True (и не равны)

7. Проверка непересечения (Disjoint)

Непересечение — множества не имеют общих элементов.

set_a = {1, 2, 3}
set_b = {4, 5, 6}
set_c = {3, 4}

# Вариант 1: метод isdisjoint()
result = set_a.isdisjoint(set_b)
print(result)  # True (нет общих элементов)

result = set_a.isdisjoint(set_c)
print(result)  # False (есть элемент 3)

# Вариант 2: проверка через пересечение
result = (set_a & set_b) == set()
print(result)  # True

# Использование: проверить, нет ли конфликтующих прав
user_permissions = {"read", "write"}
forbidden_permissions = {"delete", "admin"}
has_conflict = not user_permissions.isdisjoint(forbidden_permissions)
print(has_conflict)  # False (нет конфликта)

Мутирующие операции

set1 = {1, 2, 3}
set2 = {3, 4, 5}

# update() — объединить и изменить set1
set1_copy = set1.copy()
set1_copy.update(set2)
print(set1_copy)  # {1, 2, 3, 4, 5}

# intersection_update() — оставить только пересечение
set1_copy = set1.copy()
set1_copy.intersection_update(set2)
print(set1_copy)  # {3}

# difference_update() — удалить элементы из другого множества
set1_copy = set1.copy()
set1_copy.difference_update(set2)
print(set1_copy)  # {1, 2}

# symmetric_difference_update() — оставить только различия
set1_copy = set1.copy()
set1_copy.symmetric_difference_update(set2)
print(set1_copy)  # {1, 2, 4, 5}

Практические примеры

Пример 1: Рекомендации блогов

def recommend_blogs(user_following: set, user_followers: set) -> set:
    """
    Рекомендовать блоги, на которые подписаны мои подписчики,
    но на которые я не подписан
    """
    # Множество блогов, на которые подписаны мои подписчики
    recommended_by_followers = set()
    for follower in user_followers:
        # Получаем следующие этого подписчика
        # (это упрощённо; на практике нужен DB запрос)
        follower_following = get_following(follower)
        recommended_by_followers |= follower_following
    
    # Убираем те, на которые я уже подписан
    recommendations = recommended_by_followers - user_following
    return recommendations

my_following = {"techcrunch", "theverge", "arstechnica"}
my_followers = {"alice", "bob", "charlie"}
recommendations = recommend_blogs(my_following, my_followers)
print(recommendations)  # Неизвестные блоги

Пример 2: Аналитика: найти уникальных пользователей по дням

def unique_users_across_days(day1_users: set, day2_users: set) -> dict:
    return {
        "only_day1": day1_users - day2_users,
        "only_day2": day2_users - day1_users,
        "both_days": day1_users & day2_users,
        "total_unique": day1_users | day2_users,
    }

day1 = {"user1", "user2", "user3", "user4"}
day2 = {"user2", "user3", "user5", "user6"}

result = unique_users_across_days(day1, day2)
print(f"Only day 1: {result['only_day1']}")  # {'user1', 'user4'}
print(f"Only day 2: {result['only_day2']}")  # {'user5', 'user6'}
print(f"Both days: {result['both_days']}")    # {'user2', 'user3'}
print(f"Total unique: {result['total_unique']}")  # {user1-6}

Пример 3: Проверка прав доступа

class AccessControl:
    def __init__(self):
        self.required_permissions = {"read", "write", "delete"}
    
    def can_access(self, user_permissions: set) -> bool:
        # Пользователь может получить доступ, если у него все требуемые права
        return self.required_permissions <= user_permissions
    
    def missing_permissions(self, user_permissions: set) -> set:
        # Какие права не хватает?
        return self.required_permissions - user_permissions

acl = AccessControl()
user1_perms = {"read", "write", "delete"}  # Полный доступ
user2_perms = {"read", "write"}  # Нет delete

print(acl.can_access(user1_perms))  # True
print(acl.can_access(user2_perms))  # False
print(acl.missing_permissions(user2_perms))  # {'delete'}

Временные сложности

# Операция      |  Сложность  |  Примечание
# ───────────────┼─────────────┼──────────────────
# add()          |  O(1)       |  Average case
# remove()       |  O(1)       |  Average case
# union()        |  O(n + m)   |  n, m — размеры множеств
# intersection() |  O(min(n, m)) |  Лучше на меньшем множестве
# difference()   |  O(n)       |  Размер первого множества
# issubset()     |  O(n)       |  Размер проверяемого подмножества
# in             |  O(1)       |  Проверка принадлежности

Использование в Python

# frozenset — неизменяемое множество (можно использовать как ключ)
my_set = {1, 2, 3}
my_frozenset = frozenset([1, 2, 3])

# Использование в словаре
set_counters = {frozenset([1, 2]): 10, frozenset([3, 4]): 20}

# Set comprehension (как list comprehension)
squares = {x**2 for x in range(10)}
print(squares)  # {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

# Удаление дубликатов из списка
data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = set(data)
print(unique)  # {1, 2, 3, 4}

Итоги

• Union (|): объединяем всё
• Intersection (&): только общее
• Difference (-): только в первом
• Symmetric difference (^): различия
• Subset (<=): проверяем включение
• Superset (>=): проверяем содержание
• Disjoint: проверяем отсутствие пересечения

Множества — мощный инструмент для работы с коллекциями и логикой.