Занятие 8 Python

Методы работы со множествами

Множества работают быстрее, чем списки и кортежи, и значительно упрощают решение многих практических задач. Расскажем обо всех особенностях множеств и методах работы с ними, а в конце – порешаем задачки.

Тип данных set в Python поддерживает все операции, которые проводятся над множествами в математике:

• пересечение;
• объединение;
• дополнение;
• разность;
• симметрическую разность.

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

Особенности множеств в Python

1. В Python два вида множеств – обычное, изменяемое set и замороженное, неизменяемое frozenset. Замороженные множества нельзя изменить после создания, но все операции по объединению, пересечению и разности они поддерживают: результатом этих операций тоже будут frozenset.

2. Множество может включать в себя только неизменяемые типы данных – строки, числа, кортежи (в любой комбинации). Попытка добавить в множество список, словарь или изменяемое множество приведет к ошибке:

 >>> a_set = {[2, 3], [4, 7]}
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: unhashable type: 'list'

    

Неизменяемое множествоfrozenset, в отличие от set, может входить в изменяемое множество:

>>> set_a = {1, 2, 3}
>>> set_b = frozenset({4, 5, 6})
>>> set_c = {7, 8, 9, set_a}
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> set_c = {7, 8, 9, set_b}
>>> print(set_c)
{8, 9, frozenset({4, 5, 6}), 7}

    

3. Элементы во множествах хранятся в неупорядоченном виде, и к ним нельзя обратиться по индексу:

>>> set_a = set('123')
>>> print(set_a)
{'3', '2', '1'}
>>> print(set[1])
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: 'type' object is not subscriptable

    

4. Поскольку элементы множества не имеют индексов, срезы при работе с set тоже использовать нельзя:

>>> set_a = {1, 3, 4, 5, 2, 9, 7}
>>> print(set_a[2:5])
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: 'set' object is not subscriptable

    

5. Все элементы множества – уникальны, повторяющиеся данные в set игнорируются; это свойство множеств может пригодиться для решения практических задач:

>>> my_set = {2, 2, 2}
>>> print(my_set)
{2}

    

6. Множества не поддерживают конкатенацию и повторение:

>>> set_a = {1, 3, 5}
>>> set_b = {9, 4, 8}
>>> print(set_a + set_b)
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'set' and 'set'
>>> print(set_a * 2)
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: unsupported operand type(s) for *: 'set' and 'int'

    

7. Множества занимают значительно больший объем памяти, нежели списки и кортежи. По этой причине лучше не использовать множества для решения задач с лимитом на объем памяти:

>>> from sys import getsizeof
>>> number = 100500
>>> my_list = list(range(number))
>>> my_tuple = tuple(range(number))
>>> my_set = set(range(number))
>>> my_list_size = getsizeof(my_list)
>>> my_tuple_size = getsizeof(my_tuple)
>>> my_set_size = getsizeof(my_set)
>>> print(f'Размер списка: {round(my_list_size / 1024 / 1024, 3)} Мб')
Размер списка: 0.431 Мб
>>> print(f'Размер кортежа: {round(my_tuple_size / 1024 / 1024, 3)} Мб')
Размер кортежа: 0.383 Мб
>>> print(f'Размер множества: {round(my_set_size / 1024 / 1024, 3)} Мб')
Размер множества: 2.0 Мб

    

8. Хотя множества занимают гораздо больший объем памяти, чем списки и кортежи, работают они гораздо быстрее. Этот код сравнивает время, затраченное на проведение операции над списком, кортежем и множеством с одинаковым количеством элементов:

from time import time
number = 15000
my_set = set(range(number))
my_list = list(range(number))
my_tuple = tuple(range(number))

t = time()
for i in range(number):
    if i in my_list:
        pass
print(f"Операция со списком: {time() - t} секунд")
my_list.clear()

t = time()
for i in range(number):
    if i in my_tuple:
        pass
print(f"Операция с кортежeм: {time() - t} секунд")

t = time()
for i in range(number):
    if i in my_set:
        pass
print(f"Операция со множеством: {time() - t} секунд")
my_set.clear()

    

Результат:

Операция со списком: 1.810847282409668 секунд
Операция с кортежeм: 1.6490623950958252 секунд
Операция со множеством: 0.0013110637664794922 секунд

    

Создание множеств в Python

Пустое множество можно создать только одним способом, с помощью set():

>>> my_set = set()
>>> print(type(my_set))
<class 'set'>

    

Попытка создать пустое множество с помощью фигурных скобок {} обречена на провал – вместо setбудет создан словарь dict:

>>> my_set = {}
>>> print(type(my_set))
<class 'dict'>

    

Множество с данными можно создать несколькими способами.

Способ 1: Перечисление элементов

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

>>> set_a = {3, 7, 9, 0, 2, 1}
>>> set_b = {'а', 'б', 'в', 'г'}
>>> set_c = {'Мастер и Маргарита', 450, 1250, 'переплет'}
>>> set_d = {2, 4, 5, (2, 9, 0)}

    

Способ 2: Преобразование других типов данных

Множество можно создать на основе символов либо слов строки:

>>> print(set('абырвалг'))
{'р', 'в', 'л', 'г', 'б', 'а', 'ы'}
>>> print(set('Множества в Python'.split()))
{'Множества', 'в', 'Python'}

    

Множество из списка:

>>> print(set([3, 6, 4, 5, 5]))
{3, 4, 5, 6}

    

Множество на основе кортежа:

>>> print(set(('красный', 'синий', 'зеленый')))
{'зеленый', 'красный', 'синий'}

    

При создании множества из dict от словаря останутся только ключи:

>>> print(set({'артикул': 'А123', 'цвет': 'черный'}))
{'артикул', 'цвет'}

    

В отличие от символов строк, число нельзя автоматически разбить на отдельные цифры и преобразовать во множество напрямую:

>>> print(set(123))
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: 'int' object is not iterable

    

Но с применениемstr преобразование проходит без ошибок:

>>> print(set(str(1812)))
{'8', '2', '1'}

    

Способ 3: Генераторы множеств

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

>>> print({i ** 2 for i in range(15)})
{0, 1, 64, 121, 4, 36, 100, 196, 9, 169, 16, 49, 81, 144, 25}

    

В генераторах можно использовать любые условия:

>>> print({int(i) for i in '3в2о7ыр3р74ртрчфрежр4рфф23468795323' if i.isdigit() and int(i) < 7})
{2, 3, 4, 5, 6}

    

В генератор можно включить любые дополнительные функции, например, ввод input() и функцию ord()для возвращения числового кода символа из таблицы Unicode:

>>> print({ord(i) for i in input() if i.isalpha()})
ewr73694yrhf897349ugg05fhshcvnaWQXXldoaxsd
{81, 87, 88, 97, 99, 100, 101, 102, 103, 104, 108, 110, 111, 114, 115, 117, 118, 119, 120, 121}

    

Помимо условия if, в генератор можно добавить обработку else:

>>> set_a = {i ** 2 if i % 2 == 0 else i ** 3 for i in (map(int, input().split()))}
2 5 12 13 4 56 71 33 9 10
>>> print(set_a)
{3136, 35937, 4, 100, 144, 16, 2197, 357911, 729, 125}

    

Стандартные методы множеств в Python

Множества поддерживают ряд стандартных методов, общих для большинства коллекций Python, и имеют несколько собственных, уникальных для типа set. Начнем с общих методов.

Длина, сумма, min и max элементы

Эти методы работают со множествами точно так же, как и со списками и кортежами:

>>> set_a = {2, 4, 5, 6, 1, 9, 7, 12}
>>> print(f'Количество элементов: {len(set_a)}, сумма элементов: {sum(set_a)}')
Количество элементов: 8, сумма элементов: 46
>>> print(f'Минимальный элемент: {min(set_a)}, максимальный элемент: {max(set_a)}')
Минимальный элемент: 1, максимальный элемент: 12

    

Принадлежность элемента множеству

>>> my_set = {'математика', 'физика', 'химия'}
>>> print('математика' in my_set)
True
>>> print('биология' not in my_set)
True

    

Сортировка

Как и в случае с кортежами, результатом сортировки множества будет список:

>>> numbers = {25, 15, 7, 8, 19, 34, 52, 0, 12, 59, 91, 4}
>>> print(sorted(numbers))
[0, 4, 7, 8, 12, 15, 19, 25, 34, 52, 59, 91]
>>> print(sorted(numbers, reverse=True))
[91, 59, 52, 34, 25, 19, 15, 12, 8, 7, 4, 0]

    

Сравнение множеств

Множества можно сравнивать с помощью операторов == и !=:

>>> set_a = {5, 1, 4, 8, 6, 9}
>>> set_b = {6, 2, 5, 9, 7, 10}
>>> print(set_b != set_a)
True

    

Другие операторы сравнения, например > и <, дают неожиданный на первый взгляд результат:

>>> set_a = {1, 2, 3}
>>> set_b = {4, 5, 6, 7}
>>> print(set_b > set_a)
False

    

Это связано с тем, что при сравнении множеств Python определяет, является ли одно из них под- или надмножеством другого (подробнее об этом – ниже):

>>> set_a = {1, 2, 3}
>>> set_b = {1, 2, 3, 4}
>>> print(set_b > set_a)
True

    

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

Метод add() добавляет во множество новый элемент:

>>> letters = {'а', 'б', 'в'}
>>> letters.add('г')
>>> print(letters)
{'г', 'в', 'а', 'б'}

    

Несколько элементов можно добавить с помощью цикла for (мы рассмотрим его в следующей статье) или с помощью генератора:

>>> set_a = set()
>>> gen = {set_a.add(i) for i in range(12)}
>>> print(set_a)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

    

Удаление элемента

Для удаления элемента нужно воспользоваться одним из поддерживаемых методов:

1. remove()– возвращает сообщение об ошибке, если элемент не будет найден:

>>> my_set = {1, 2, 3}
>>> my_set.remove(2)
>>> print(my_set)
{1, 3}

    

2. discard() – безопасный метод, не приводит к ошибке в случае отсутствия элемента:

>>> my_set = {'красный', 'черный', 'синий'}
>>> my_set.discard('синий')
>>> print(my_set)
{'красный', 'черный'}
>>> my_set.discard('розовый')
>>> 

    

3. pop() – в отличие от аналогичного списочного метода, удаляет случайный элемент и возвращает его значение:

>>> my_set = {2, 4, 6, 1, 12}
>>> print(my_set.pop())
1

    

4. Метод clear() удаляет все элементы множества сразу – так можно освободить оперативную память после завершения операции с объемным set:

>>> my_set = {6, 2, 9, 0}
>>> my_set.clear()
>>> print(my_set)
set()

    

Специальные методы множеств

Как уже упоминалось выше, объекты setв Python поддерживают все операции, которые проводятся над множествами в математике. Эти операции делятся на три группы:

• Не изменяющие исходные множества – эти методы возвращают новые множества.
• Изменяющие исходные множества.
• Определяющие, являются ли множества под(над)множествами друг друга – эти методы возвращают True или False.

Рассмотрим методы из этих групп подробнее.

Методы, не изменяющие исходные множества

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

Объединение множеств union () – это множество, которое состоит из элементов, входящих в состав хотя бы одного из объединяемых множеств:

>>> set_a = {1, 2, 3}
>>> set_b = {4, 5, 6}
>>> print(set_a.union(set_b))
{1, 2, 3, 4, 5, 6}

    

Вместо union() можно использовать оператор |:

>>> set_a = {'синий', 'розовый', 'черный'}
>>> set_b = {'зеленый', 'красный', 'желтый'}
>>> print(set_a | set_b)
{'синий', 'красный', 'желтый', 'розовый', 'черный', 'зеленый'}

    

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

Пересечением множествintersection() называется множество, которое состоит из элементов, входящих в каждое из пересекающихся множеств:

>>> set_a = {2, 3, 5, 1, 8}
>>> set_b = {2, 5, 0, 9, 7}
>>> print(set_a.intersection(set_b))
{2, 5}

    

Вместо intersection() можно использовать оператор &:

>>> set_a = {'a', 'b', 'd', 'k'}
>>> set_b = {'v', 'b', 'e', 'k'}
>>> print(set_a & set_b)
{'k', 'b'}

    

Разность множеств

Разностью множеств difference()называется множество, в которое входят все элементы первого множества, не входящие во второе множество:

>>> set_a = {4, 9, 7, 2, 1, 0}
>>> set_b = {5, 8, 3, 1, 4, 9}
>>> print(set_a.difference(set_b))
{0, 2, 7}

    

Вместо difference() можно использовать оператор - :

>>> set_a = {'a', 'b', 'g', 'j'}
>>> set_b = {'f', 'b', 's', 'g'}
>>> print(set_a - set_b)
{'a', 'j'}

    

Симметрическая разность

Симметрической разностью symmetric_difference()называется множество, состоящее из элементов, которые не входят в первое и второе множество одновременно:

>>> set_a = {1, 2, 3, 4}
>>> set_b = {6, 8, 4, 3}
>>> print(set_a.symmetric_difference(set_b))
{1, 2, 6, 8}

    

В качестве оператора симметрической разности используется ^:

>>> set_a = {'h', 'v', 'a', 'w', 'q'}
>>> set_b = {'v', 'h', 'u', 'f', 'o'}
>>> print(set_a ^ set_b)
{'u', 'w', 'f', 'q', 'a', 'o'}

    

Методы, изменяющие исходные множества

Метод update()

Изменяет исходное множество по объединению:

>>> set_a = {1, 2, 3}
>>> set_b = {4, 5, 6}
>>> set_a.update(set_b)
>>> print(set_a)
{1, 2, 3, 4, 5, 6}

    

Оператор метода update – |=:

>>> set_a = {'a', 'b', 'd'}
>>> set_b = {'c', 'e', 'f'}
>>> set_a |= set_b
>>> print(set_a)
{'b', 'c', 'f', 'a', 'e', 'd'}

    

Метод intersection_update()

Изменяет исходное множество по пересечению:

>>> set_a = {1, 2, 3}
>>> set_b = {3, 4, 5}
>>> set_a.intersection_update(set_b)
>>> print(set_a)
{3}

    

Оператор intersection_update() – &=:

>>> set_a = {'a', 'b', 'd', 'q'}
>>> set_b = {'h', 'f', 'b', 'a'}
>>> set_a &= set_b
>>> print(set_a)
{'a', 'b'}

    

Метод difference_update()

Изменяет исходное множество по разности:

>>> set_a = {3, 2, 7, 8, 0}
>>> set_b = {4, 5, 6, 3, 8}
>>> set_a.difference_update(set_b)
>>> print(set_a)
{0, 2, 7}

    

Операторdifference_update() – -=:

>>> set_a = {'v', 's', 'a', 'q', 'r'}
>>> set_b = {'d', 's', 'a', 'f', 'e'}
>>> set_a -= set_b
>>> print(set_a)
{'q', 'r', 'v'}

    

Метод symmetric_difference_update()

Изменяет исходное множество по симметрической разности:

>>> set_a = {1, 2, 3, 4, 5}
>>> set_b = {8, 2, 4, 6, 1}
>>> set_a.symmetric_difference_update(set_b)
>>> print(set_a)
{3, 5, 6, 8}

    

Оператор symmetric_difference_update()– ^=:

>>> set_a = {'a', 'k', 'r', 'o', 'p'}
>>> set_b = {'d', 'a', '$', 'o', '@'}
>>> set_a ^= set_b
>>> print(set_a)
{'@', 'p', 'd', 'k', 'r', '$'}

    

Методы для определения под- и надмножеств

Множество set_a считается подмножеством set_b в том случае, если все элементы set_a входят в set_b. В свою очередь, множество set_b этом случае считается надмножеством set_a. При этом любое множество считается подмножеством самого себя, или нестрогим подмножеством.

Для определения под- и надмножеств в Python есть три метода:

1. issuperset()– возвращает True, если первое множество является подмножеством второго, и False в обратном случае. Такой же результат можно получить с помощью операторов < (строгое подмножество) и <= (нестрогое подмножество):

>>> set_a = {1, 2, 3}
>>> set_b = {4, 5, 1, 2, 3}
>>> print(set_a.issubset(set_b))
True
>>> print(set_a <= set_b)
True
>>> print(set_a < set_b)
True

    

2. issubset()– возвращает True, если одно множество является надмножеством другого, иFalse в противном случае. Аналог – операторы > (строгое надмножество) и >= (нестрогое надмножество):

>>> set_a = {'XS', 'S', 'M', 'L', 'XL', 'XXL'}
>>> set_b = {'S', 'M', 'L'}
>>> print(set_a.issuperset(set_b))
True
>>> print(set_a > set_b)
True
>>> print(set_a >= set_b)
True

    

3.isdisjoint() – возвращает True, если множества не имеют общих элементов, и False, если такие элементы есть:

>>> set_a = {1, 2, 3}
>>> set_b = {4, 5, 6}
>>> set_c = {1, 3, 5}
>>> print(set_a.isdisjoint(set_b))
True
>>> print(set_c.isdisjoint(set_b))
False

    

Практика

Задание 1

Напишите программу, которая получает на вход три слова и определяет, являются ли они анаграммами друг друга.

Пример ввода:

кластер
стрелка
сталкер

    

Вывод:

        Да
    

Решение:

set_a, set_b, set_c = set(input()), set(input()), set(input()) print('Да' if set_a == set_b == set_c else 'Нет')

Задание 2

Напишите программу, которая получает на вход две строки с перечислением интересов и хобби двух пользователей, и вычисляет процент совпадения.

Пример ввода:

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

    

Вывод:

        Совпадение интересов: 27.27%
    

Решение:

hobbies1 = input().split()
hobbies2 = input().split()
result = len(set(hobbies1) & set(hobbies2)) / float(len(set(hobbies1) | set(hobbies2))) * 100
print(f'Совпадение интересов: {result:.2f}%')

    

Задание 3

Напишите программу, которая получает на вход строку, и определяет, является ли строка панграммой (т.е.содержатся ли в ней все 33 буквы русского алфавита).

Пример ввода:

Широкая электрификация южных губерний даст мощный толчок подъёму сельского хозяйства
    

Вывод:

        Да
    

Решение:

result = {i.lower() for i in input() if i.isalpha()}
print('Да' if len(result) == 33 else 'Нет')

    

Задание 4

Напишите программу, которая получает n слов, и вычисляет количество уникальных символов во всех словах.

Пример ввода:

5
программа
код
компьютер
монитор
интерпретатор

    

Вывод:

        Количество уникальных символов во всех словах: 14
    

Решение:

n = int(input())
print('Количество уникальных символов во всех словах:', len(set(''.join([input().lower() for _ in range(n)]))))

    

Задание 5

Напишите программу, которая:

• Получает на вход две строки, в которых перечисляются книги, прочитанные двумя учениками.
• Выводит количество книг, которые прочитали оба ученика.

Пример ввода:

Мастер и Маргарита, Война и мир, Тихий Дон, Евгений Онегин
Джейн Эйр, Террор, Война и мир, Мастер и Маргарита, Нос

    

Вывод:

        2
    

Решение:

print(len(set(input().split(', ')) & set(input().split(', '))))
    

Задание 6

Напишите программу, которая получает от пользователя две строки с числами, и выводит в порядке возрастания числа, встречающиеся в обеих строках.

Пример ввода:

4 12 6 11 0 8 7 5 1 25
2 1 4 5 56 6 8 7 14 33

    

Вывод:

        1 4 5 6 7 8
    

Задание 7

Напишите программу, которая получает два числа и выводит Есть, если числа содержат общие цифры, и Нет в противном случае.

Пример ввода:

5678
3421

    

Вывод:

        Нет
    

Решение:

print('Есть' if set(input()) & set(input()) else 'Нет')
    

Задание 8

Напишите программу, которая получает строку с именами файлов, и выводит уникальные имена .jpg файлов, отсортированные в алфавитном порядке.

Пример ввода:

book_cover.jpg cover.png Book_cover.jpg illustration.jpg ILLUSTRATION.JPG my_cover.png photo.gif award.jpg Award.jpg award.JPG
    

Вывод:

        award.jpg book_cover.jpg illustration.jpg
    

Решение:

files = input().split()
result = {i.lower() for i in files if i.lower().endswith('.jpg')}
print(*sorted(result))

    

Задание 9

Два дизайнера поспорили о том, кто из них знает больше оттенков цветов. Они перечисляют оттенки, но иногда забывают о том, что уже называли какой-то тон. Напишите программу, которая получает на вход n строк с названиями оттенков, и определяет, есть ли среди них повторы. Если повтор есть, нужно вывести Повтор, если нет – Принято.

Пример ввода:

6
аспидно-серый
Бананомания
аквамариновый
Баклажановый
агатовый
антрацитовый

    

Вывод:

        Принято
    

Решение:

colors = [input().lower() for _ in range(int(input()))] print('Повтор!' if len(colors) > len(set(colors)) else 'Принято')

Задание 10

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

• Сначала программа получает список из m продуктов, которые есть в кладовой.
• Затем получает n ингредиентов, необходимых для рецепта.
• Выводит Есть, если ингредиент имеется в кладовой, и Отсутствует в противном случае.

Пример ввода:

6
5
мука
сахар
Сода
яйца
масло сливочное
масло растительное
Сахар
Мука
Яйца
сливки
масло сливочное

    

Вывод:

Есть
Есть
Есть
Отсутствует
Есть

    

Решение:

m, n = [int(input()) for _ in 'mn']
pantry = {input().lower() for _ in range(m)}

Подведем итоги

Множества позволяют просто и лаконично решать задачи, связанные с уникальностью, вхождением элементов в определенные группы и совпадением (расхождением) в составе групп. Однако множества в Python имеют серьезный недостаток – они занимают значительный объем памяти, что может стать проблемой при решении олимпиадных задач. В следующей статье будем изучать цикл for.