discrete math in python: homework 2

Дед Мороз готовит подарки к Новому году. У Деда Мороза есть заводной
автомобиль, книжка–раскраска, кукла Таня, кулек конфет и еще n - 4
различных подарка. Каждый из них имеется в неограниченном количестве,
так что проблем вроде бы быть не должно. Однако Деду Морозу кажется, что
кулек конфет и заводной автомобиль — неравноценные подарки, поэтому к
кульку конфет он, скорее всего, добавит книжку–раскраску или что-то еще.
Дед Мороз уже составил k подарочных наборов, каждый из которых содержит
не более одного подарка каждого типа (т.е. в одном наборе — не более
одной куклы Тани). Принципы Деда Мороза не позволяют ему дарить одному
ребенку явно больше, чем другому, поэтому каждый из любых двух наборов
содержит какой-то подарок, которого нет в другом наборе. Дед Мороз
пытается составить еще один — (k + 1)-ый — подарочный набор,
согласующийся с его принципами, но у него не получается.

Напишите функцию another_gift(items, gifts), получающую на вход
множество (frozenset) типов подарков items и список (list) подарочных
наборов (frozenset) gifts, каждый из которых является подмножеством
items и не является подмножеством никакого другого набора из списка
gifts. Функция возвращает еще один такой подарочный набор, если таковой
существует, и None — в противном случае.

Например, вызов функции

another_gift(frozenset([1, 2, 3, 4]),
             [frozenset([1, 2]), frozenset([2, 3, 4])])

может вернуть frozenset([1, 3]), или frozenset([1, 4]), или
frozenset([1, 3, 4]). Вызов же функции

another_gift(frozenset([1, 2, 3]),
             [frozenset([1, 2]), frozenset([3])])

должен вернуть None.

Приведите и обоснуйте теоретическую оценку времени работы функции в
худшем случае.

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>