В статье рассматриваются решения пяти типовых задач, в которых отрабатываются навыки работы со множествами.
Множество в python - это структура данных (контейнер), которая содержит не повторяющиеся элементы в случайном порядке.
Встречалось ли число раньше.
Дана строка, в которой записана последовательность чисел через пробел. Необходимо для каждого числа вывести слово YES , если это число встречалось уже ранее в последовательности или вывести NO, если не это число не встречалось.
Входные данные: 1 2 3 2 3 4
Вывод программы: NO NO NO YES YES NO. Каждое слово на своей строке.
n = map(int, input().split())
m = set()
for i in n:
....if i in m:
........print('YES')
....else:
........print('NO')
........m.add(i)
Кубики.
Таня и Коля любят играть в разноцветные кубики. У каждого из детей свой набор кубиков и в каждом наборе все они различаются по цвету. Детям стало интересно, сколько существуют таких цветов, что кубики каждого цвета есть и в наборе Тани и в наборе Коли. Для этого они пронумеровали все цвета случайными целыми числами в пределах от 0 до 10⁹. Что делать дальше они не знают. Помогите детям решить задачу.
Во входном файле в первой строке записаны числа N и M — это количество кубиков у Тани и Коли соответственно. Дальше идут N строк с номерами цветов кубиков Тани. В последних M строках записаны номера цветов кубиков Коли.
Нужно сначала вывести количество, а потом номера цветов кубиков, цвета которых есть в обоих наборах. Далее вывести количество и номера цветов, которые остались у Тани, а затем количество и номера остальных цветов у Коли. Все наборы выводимых цветов необходимо отсортировать по возрастанию.
Входные данные: 4 3 \n 0 \n 1 \n 10 \n 9 \n 1 \n 3 \n 0 ( \n - перенос строки)
Вывод программы: 2 \n 0 1 \n 2 \n 9 10 \n 1 \n 3
inFile = open('input.txt', 'r', encoding='utf8')
i = 0
nset = set()
mset = set()
for line in inFile:
....if i == 0:
........n = int(line.split()[0])
........m = int(line.split()[1])
....if i > 0 and i <= n:
........nset.add(int(line))
....elif i > n:
........mset.add(int(line))
....i += 1
inFile.close()
print(len(nset & mset))
print(*sorted(list(nset & mset)))
print(len(nset - mset))
print(*sorted(list(nset - mset)))
print(len(mset - nset))
print(*sorted(list(mset - nset)))
Множество nset - цвета кубиков Тани, mset - цвета кубиков Коли. Для обоих множеств находим пересечение nset & mset - это цвета и у Тани, и у Коли. Цвета только у Тани это nset - mset, цвета только у Коли mset - nset.
Количество слов в тексте.
Во входном файле input.txt записан текст. Слово - это последовательность символов идущих подряд без пробелов. Слова разделяются одним или несколькими пробелами, а так же символами конца строки. Найдите, сколько разных слов содержит этот текст.
inFile = open('input.txt', 'r', encoding='utf8')
n = set()
for line in inFile:
....line1 = line.split()
....for ind in line1:
........n.add(ind.rstrip('\n'))
inFile.close()
print(len(n))
Множества отлично подходят для подсчета количества уникальных слов, так как множество не может содержать двух одинаковых значений.
Угадай число (часть 1).
Коля и Таня играют в игру. Коля загадал натуральное число от 1 до n. Таня, для того чтобы угадать это число, называет некоторые множества натуральных чисел. Коля отвечает Тане YES, если среди названных ею чисел есть задуманное им число или NO если нет. Задав несколько вопросов, Таня запуталась во множестве чисел и просит вас помочь ей понять, какие числа мог задумать Коля.
Во входных данных первая строка содержит число n — максимальное число, которое мог загадать Коля. Затем ниже идут строки, которые содержат вопросы Тани. Каждая строка это числа, разделенные пробелами. После каждой строки с вопросом от Тани следует ответ Коли: YES или NO. Слово HELP означает последнюю строку входных данных.
В ответе необходимо вывести все числа, которые мог задумать Коля. Каждое число выводится через пробел, набор чисел должен быть в порядке возрастания.
Входные данные: 10 \n 1 2 3 4 5 \n YES \n 2 4 6 8 10 \n NO \n HELP
Вывод программы: 1 3 5
inFile = open('input.txt', 'r', encoding='utf8')
i = 0
n = set()
for line in inFile:
....line = line.rstrip('\n')
....if i == 0:
........for j in range(1, int(line) + 1):
............n.add(j)
....elif i > 0 and line == 'HELP':
........print(*sorted(n))
........break
....elif i > 0 and i % 2 != 0:
........m = set(list(map(int, line.split())))
....elif i > 0 and i % 2 == 0:
........if line == 'YES':
............n &= m
........else:
............n -= m
....i += 1
inFile.close()
Имея наибольшее возможное число n, загаданное Колей, создаем множество чисел от 0 до n:
........for j in range(1, int(line) + 1):
............n.add(j)
Затем, если номер строки файла i нечетный, значит это множество чисел Тани. Его записываем в m. Если номер строки файла i четный, значит это ответ Коли. В зависимости от ответа в n записываем или пересечение множеств n &= m, или разность n -= m. После слова HELP выводим оставшиеся в n числа print(*sorted(n)).
Угадай число (часть 2).
Коля и Таня продолжают играть в игру, но Коля начал жульничать. Теперь на при ответе на вопрос Тани он выбирает такой вариант ответа YES или NO, чтобы количество возможных загаданных им чисел оставалось как можно больше. Например, если Коля загадал число от 1 до 5, а Таня спросила про числа 1 и 2, то Коля ответит NO, так как это множество меньше оставшегося, а если Таня спросит про 1, 2, 3, то Коля ответит YES. В случае если Таня в своем вопросе называет ровно половину из загаданных чисел, то Коля из вредности своего характера всегда отвечает NO. К счастью, Коля при ответе учитывает все предыдущие вопросы Тани и то, как он отвечал на них раньше, то есть множество возможных загаданных Колей чисел уменьшается.
Вам задана последовательность вопросов Тани. Выведите ответы Коли на них. Во входных данных в первой строке число n — максимальное число, которое мог задумать Коля. Дальше идут строки, в которых содержатся вопросы Тани. Каждая строка содержит набор чисел, разделенных пробелами. Слово HELP означает конец входных данных.
На каждый вопрос Тани выведите ответ Коли на этот вопрос. Затем выведите все числа, которые мог задумать Коля. Числа выведите через пробел и в порядке возрастания.
Входные данные: 10 \n 1 2 3 4 5 \n 2 4 6 8 10 \n HELP
Вывод программы: NO \n YES \n 6 8 10
inFile = open('input.txt', 'r', encoding='utf8')
i = 0
possibleSet = set()
for line in inFile:
....line = line.rstrip('\n')
....if i == 0:
........for j in range(1, int(line) + 1):
............possibleSet.add(j)
....elif i > 0 and line == 'HELP':
........print(*sorted(possibleSet))
........break
....elif i > 0:
........tanyaSet = set(list(map(int, line.split())))
........if 2 * len(possibleSet & tanyaSet) <= len(possibleSet):
............print('NO')
............possibleSet -= tanyaSet
........else:
............print('YES')
............possibleSet &= tanyaSet
....i += 1
inFile.close()
Как и в предыдущей задаче создаем множество чисел possibleSet от 0 до n возможных задуманных Колей. Далее смотрим, если удвоенное количество элементов пересечения возможного множества с множеством Тани не больше количества элементов возможного множества if 2 * len(possibleSet & tanyaSet) <= len(possibleSet):, то печатаем NO и вычитаем possibleSet -= tanyaSet. В противном случае печатаем YES и пересекаем possibleSet &= tanyaSet.
Заключение.
Групповые операции над множествами:
A | B Объединение множеств
A & B Пересечение множеств
A - B Множество, элементы которого входят в A, но не входят в B
A ^ B Элементы входят в A | B, но не входят в A & B
Результатом этих операций будет созданное новое множество. Предусмотрена для этих операций и сокращенная запись: |=, &=, -= и ^=. Программы с такими записями работают быстрее.
Операции сравнения:
A == B Все элементы совпадают (порядок может не совпадать)
A != B Есть различные элементы
A <= B Все элементы A входят в B
