Множествa или set в python

Множество - неупорядоченная структура данных с уникальными элементами. Как и словари, оформляются фигурными скобками, не имеют индексов.

У множеств (как и у словарей) высокая скорость поиска, гораздо выше, чем у списков.
Множество похоже на словарь, в котором значения отброшены, а оставлены только ключи. Как и в словаре, ключи должны быть уникальными.

Юзай множество, если нужно просто узнать, существует элемент в нем или нет (все остальное неважно).

Создание пустого множества

Python

>>> set1 = set()
>>> set1
set()

Не юзай {} для создания множества

{} используются для создания словарей:

Python

>>> dict1 = {}
>>> type(dict1)
<class 'dict'>

>>> set1 = set()
>>> type(set1)
<class 'set'>

Всё так, ибо словари в Python появились раньше и взяли себе {}.

Преобразование в множество

Python

# Строка:
>>> set('letttters')
{'s', 'r', 'l', 'e', 't'}

# Список:
>>> set(['Dasher', 'Dancer', 'Prancer', 'Mason-Dixon'])
{'Dancer', 'Dasher', 'Mason-Dixon', 'Prancer'}

# Кортеж:
>>> set(('Ummagumma', 'Echoes', 'Atom Heart Mother'))
{'Ummagumma', 'Atom Heart Mother', 'Echoes'}

# Из словаря вернутся ТОЛЬКО КЛЮЧИ:
>>> set({'apple': 'red', 'orange': 'orange', 'cherry': 'red'})
{'cherry', 'orange', 'apple'}

Добавление элемента с помощью `add()`

Python

>>> s = set((1,2,3))
>>> s
{1, 2, 3}
>>> s.add(4)
>>> s
{1, 2, 3, 4}

Удаление элемента с помощью `remove()`

Python

>>> s = set((1,2,3))
>>> s.remove(3)
>>> s
{1, 2}

Включение множества (set comprehensions)

Синтаксик:

Python

{ выражение for выражение in итерабельный объект}
{ выражение for выражение in итерабельный объект if условие }

Пример:

Python

>>> a_set = {number for number in range(1,6) if number % 3 == 1}
>>> a_set
{1, 4}

Замороженное множество. `frozenset()`

Если нужно создать множество, которое нельзя будет изменить - есть функция frozenset():

Python

# Список
>>> frozenset([3, 2, 1])
frozenset({1, 2, 3})
# Множество
>>> frozenset(set([2, 1, 3]))
frozenset({1, 2, 3})
>>> frozenset({3, 1, 2})
frozenset({1, 2, 3})
# Кортеж
>>> frozenset( (2, 3, 1) )
frozenset({1, 2, 3})

В чем "замороженность"?

Python

>>> fs = frozenset([3, 2, 1])
>>> fs
frozenset({1, 2, 3})
>>> fs.add(4)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    fs.add(4)
     ^^^^^^
AttributeError: 'frozenset' object has no attribute 'add'

Пересечение множеств. Метод `.intersection()` или `&`

Это всё, кстати - уже алгебра.
Найти пересечение одного множества с другим можно так:

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a & b
{3, 4}
>>> a.intersection(b)
{3, 4}

Объединение множеств. Метод `.union()` или `|`

Объединить множества можно так:

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a | b
{1, 2, 3, 4, 5, 6}
>>> a.union(b)
{1, 2, 3, 4, 5, 6}

Разность множеств. Метод `.difference()` или `-`

Разностью двух множеств называется множество, состоящее из тех и только тех элементов, которые входят в первое множество, но не входят во второе.

250

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a - b
{1, 2}
>>> a.difference(b)
{1, 2}

Исключающее ИЛИ. Функция `symmetric_difference()` или оператор `^`

Позволяет найти элементы или первого, или второго множества, но не общие:

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a ^ b
{1, 2, 5, 6}
>>> a.symmetric_difference(b)
{1, 2, 5, 6}

Подмножество. Функция `issubset()` или операторы `<=`, `<`

Позволяет проверить, является ли одно множество подмножеством другого (когда все члены первого множества являются членами второго):

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a <= b
False
>>> a.issubset(b)
False

Для того чтобы стать собственным подмножеством, второе множество должно содержать все члены первого и несколько других. Определяется это с помощью оператора <:

Python

>>> a < b
False
>>> a < a
False

Надмножества. Функция `issuperset()` или операторы `>=`, `>`

Надмножество противоположно подмножеству (все члены второго множества являются также членами первого). Для определения этого используется оператор >= или функция issuperset():

Python

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}

>>> a >= b
False
>>> a.issuperset(b)
False

Любое множество является надмножеством самого себя:

Python

>>> a >= a
True
>>> a.issuperset(a)
True

Можно проверить правильное надмножество (первое множество содержит все члены второго и несколько других) с помощью оператора >:

Python

>>> a > b
False

Множество не может быть правильным надмножеством самого себя:

Python

>>> a > a
False

Другие методы множеств и операции с множествами

Методы множеств

Метод	Что делает метод
nums.add(elem)	добавляет элемент в множество
nums.remove(elem)	удаляет элемент из множества. KeyError, если такого элемента не существует
nums.discard(elem)	удаляет элемент, если он находится в множестве. Если элемента нет, то ничего не происходит
nums.pop()	удаляет первый элемент из множества. Так как множества не упорядочены, нельзя точно сказать, какой элемент будет первым
nums.clear()	очистка множества
#### Операции со множествами

Операция	Метод	Что делает операция
A \| B	A.union(B)	Возвращает множество, являющееся объединением множеств A и B
A \|= B	A.update(B)	Добавляет в множество A все элементы из множества B
A & B	A.intersection(B)	Возвращает множество, являющееся пересечением множеств A и B
A &= B	A.intersection_update(B)	Оставляет в множестве A только те элементы, которые есть в множестве B
A - B	A.difference(B)	Возвращает разность множеств A и B (элементы, входящие в A, но не входящие в B)
A -= B	A.difference_update(B)	Удаляет из множества A все элементы, входящие в B

Проверка наличия значения с помощью оператора `in`

Это самый распространенный сценарий использования множеств:

Python

>>> drinks = {
    'martini': {'vodka', 'vermouth'},
    'black russian': {'vodka', 'kahlua'},
    'white russian': {'cream', 'kahlua', 'vodka'},
    'manhattan': {'rye', 'vermouth', 'bitters'},
    'screwdriver': {'orange juice', 'vodka'}
}
>>> for name, contents in drinks.items():
        if 'vodka' in contents:
            print(name)

martini
black russian
white russian
screwdriver


>>> for name, contents in drinks.items():
        if 'vodka' in contents and not ('vermouth' in contents or
                                        'cream' in contents):
            print(name)

screwdriver
black russian

Если нужно проверить наличие сразу нескольких значений множества: допустим, нужен напиток с апельсиновым соком или вермутом. Для юзай оператор пересечения множеств &:

Python

>>> for name, contents in drinks.items():
        if contents & {'vermouth', 'orange juice'}:
            print(name)

screwdriver
martini
manhattan

Результатом работы оператора & является множество со всеми элементами из обоих сравниваемых списков. Если ни один из заданных ингредиентов не содержится в предлагаемых коктейлях, оператор & вернет пустое множество. Этот результат можно считать равным False.

Или если нужна водка, не смешанная со сливками или вермутом:

Python

>>> for name, contents in drinks.items():
        if 'vodka' in contents and not contents & {'vermouth', 'cream'}:
            print(name)

screwdriver
black russian

fck alcohol

Алгоритмическая сложность методов множества

Добавление элемента в множество `add`

средний случай: $O(1)$
худший случай: $O(n)$, где $n$ - размер множества
Худший случай происходит, когда случается коллизия хешей и требуется перехеширование и перестроение множества.

Поиск элемента в множестве `in`

средний случай: $O(1)$
худший случай: $O(n)$, где $n$ - размер множества
В худшем случае поиск может пройти через все элементы множества.

Удаление элемента из множества `remove`, `discard`

средний случай: $O(1)$
худший случай: $O(n)$
В худшем случае удаление может потребовать перестроения множества после завершения процесса.

Объединение множеств `union`

средний случай: $O(min(len(set1), len(set2)))$
$set1$ и $set2$ - размеры двух объединяемых множеств
худший случай: $O(len(set1) + len(set2))$

Пересечение множеств `intersection`

средний случай: $O(min(len(set1), len(set2)))$
худший случай: $O(min(len(set1), len(set2)))$

Соус: Книга "Простой Python" --> Глава 8. "Словари и множества"

Множествa или set в python

Создание пустого множества

Преобразование в множество

Добавление элемента с помощью add()

Удаление элемента с помощью remove()

Включение множества (set comprehensions)

Замороженное множество. frozenset()

Пересечение множеств. Метод .intersection() или &

Объединение множеств. Метод .union() или |

Разность множеств. Метод .difference() или -

Исключающее ИЛИ. Функция symmetric_difference() или оператор ^

Подмножество. Функция issubset() или операторы <=, <

Надмножества. Функция issuperset() или операторы >=, >

Другие методы множеств и операции с множествами

Методы множеств

Проверка наличия значения с помощью оператора in

Алгоритмическая сложность методов множества

Добавление элемента в множество add

Поиск элемента в множестве in

Удаление элемента из множества remove, discard

Объединение множеств union

Пересечение множеств intersection

python

Добавление элемента с помощью `add()`

Удаление элемента с помощью `remove()`

Замороженное множество. `frozenset()`

Пересечение множеств. Метод `.intersection()` или `&`

Объединение множеств. Метод `.union()` или `|`

Разность множеств. Метод `.difference()` или `-`

Исключающее ИЛИ. Функция `symmetric_difference()` или оператор `^`

Подмножество. Функция `issubset()` или операторы `<=`, `<`

Надмножества. Функция `issuperset()` или операторы `>=`, `>`

Проверка наличия значения с помощью оператора `in`

Добавление элемента в множество `add`

Поиск элемента в множестве `in`

Удаление элемента из множества `remove`, `discard`

Объединение множеств `union`

Пересечение множеств `intersection`