# В домашней работе вам надо будет сгенерировать свой вариант следующим образом
def generate(key, problems=4, variants=4):
r = 0
for c in key:
r += ord(c)
result = []
for j in range(problems):
result.append(chr(ord('A') + j) + str(r % variants + 1))
r //= variants
return result
generate("Зобнин Алексей Игоревич")
['A1', 'B1', 'C2', 'D3']
# Рассмотрим модуль itertools
# Подключить его можно так:
import itertools
# Но тогда придется писать itertools. перед каждым именем функции из этого модуля
# Поэтому сделаем так:
from itertools import *
# Вообще-то так писать в больших проектах не рекомендуется,
# чтобы не засорять пространства имен. Лучше подключать только нужные имена
s = [1, 2, 3, 4]
# Сгенерируем перестановки элементов списка
for p in permutations(s):
print(p)
(1, 2, 3, 4) (1, 2, 4, 3) (1, 3, 2, 4) (1, 3, 4, 2) (1, 4, 2, 3) (1, 4, 3, 2) (2, 1, 3, 4) (2, 1, 4, 3) (2, 3, 1, 4) (2, 3, 4, 1) (2, 4, 1, 3) (2, 4, 3, 1) (3, 1, 2, 4) (3, 1, 4, 2) (3, 2, 1, 4) (3, 2, 4, 1) (3, 4, 1, 2) (3, 4, 2, 1) (4, 1, 2, 3) (4, 1, 3, 2) (4, 2, 1, 3) (4, 2, 3, 1) (4, 3, 1, 2) (4, 3, 2, 1)
len(list(itertools.permutations(s)))
24
# Переставлять можно элементы любой итерируемой сущности. Например, буквы в строке
for p in permutations("hello"):
print(p)
('h', 'e', 'l', 'l', 'o') ('h', 'e', 'l', 'o', 'l') ('h', 'e', 'l', 'l', 'o') ('h', 'e', 'l', 'o', 'l') ('h', 'e', 'o', 'l', 'l') ('h', 'e', 'o', 'l', 'l') ('h', 'l', 'e', 'l', 'o') ('h', 'l', 'e', 'o', 'l') ('h', 'l', 'l', 'e', 'o') ('h', 'l', 'l', 'o', 'e') ('h', 'l', 'o', 'e', 'l') ('h', 'l', 'o', 'l', 'e') ('h', 'l', 'e', 'l', 'o') ('h', 'l', 'e', 'o', 'l') ('h', 'l', 'l', 'e', 'o') ('h', 'l', 'l', 'o', 'e') ('h', 'l', 'o', 'e', 'l') ('h', 'l', 'o', 'l', 'e') ('h', 'o', 'e', 'l', 'l') ('h', 'o', 'e', 'l', 'l') ('h', 'o', 'l', 'e', 'l') ('h', 'o', 'l', 'l', 'e') ('h', 'o', 'l', 'e', 'l') ('h', 'o', 'l', 'l', 'e') ('e', 'h', 'l', 'l', 'o') ('e', 'h', 'l', 'o', 'l') ('e', 'h', 'l', 'l', 'o') ('e', 'h', 'l', 'o', 'l') ('e', 'h', 'o', 'l', 'l') ('e', 'h', 'o', 'l', 'l') ('e', 'l', 'h', 'l', 'o') ('e', 'l', 'h', 'o', 'l') ('e', 'l', 'l', 'h', 'o') ('e', 'l', 'l', 'o', 'h') ('e', 'l', 'o', 'h', 'l') ('e', 'l', 'o', 'l', 'h') ('e', 'l', 'h', 'l', 'o') ('e', 'l', 'h', 'o', 'l') ('e', 'l', 'l', 'h', 'o') ('e', 'l', 'l', 'o', 'h') ('e', 'l', 'o', 'h', 'l') ('e', 'l', 'o', 'l', 'h') ('e', 'o', 'h', 'l', 'l') ('e', 'o', 'h', 'l', 'l') ('e', 'o', 'l', 'h', 'l') ('e', 'o', 'l', 'l', 'h') ('e', 'o', 'l', 'h', 'l') ('e', 'o', 'l', 'l', 'h') ('l', 'h', 'e', 'l', 'o') ('l', 'h', 'e', 'o', 'l') ('l', 'h', 'l', 'e', 'o') ('l', 'h', 'l', 'o', 'e') ('l', 'h', 'o', 'e', 'l') ('l', 'h', 'o', 'l', 'e') ('l', 'e', 'h', 'l', 'o') ('l', 'e', 'h', 'o', 'l') ('l', 'e', 'l', 'h', 'o') ('l', 'e', 'l', 'o', 'h') ('l', 'e', 'o', 'h', 'l') ('l', 'e', 'o', 'l', 'h') ('l', 'l', 'h', 'e', 'o') ('l', 'l', 'h', 'o', 'e') ('l', 'l', 'e', 'h', 'o') ('l', 'l', 'e', 'o', 'h') ('l', 'l', 'o', 'h', 'e') ('l', 'l', 'o', 'e', 'h') ('l', 'o', 'h', 'e', 'l') ('l', 'o', 'h', 'l', 'e') ('l', 'o', 'e', 'h', 'l') ('l', 'o', 'e', 'l', 'h') ('l', 'o', 'l', 'h', 'e') ('l', 'o', 'l', 'e', 'h') ('l', 'h', 'e', 'l', 'o') ('l', 'h', 'e', 'o', 'l') ('l', 'h', 'l', 'e', 'o') ('l', 'h', 'l', 'o', 'e') ('l', 'h', 'o', 'e', 'l') ('l', 'h', 'o', 'l', 'e') ('l', 'e', 'h', 'l', 'o') ('l', 'e', 'h', 'o', 'l') ('l', 'e', 'l', 'h', 'o') ('l', 'e', 'l', 'o', 'h') ('l', 'e', 'o', 'h', 'l') ('l', 'e', 'o', 'l', 'h') ('l', 'l', 'h', 'e', 'o') ('l', 'l', 'h', 'o', 'e') ('l', 'l', 'e', 'h', 'o') ('l', 'l', 'e', 'o', 'h') ('l', 'l', 'o', 'h', 'e') ('l', 'l', 'o', 'e', 'h') ('l', 'o', 'h', 'e', 'l') ('l', 'o', 'h', 'l', 'e') ('l', 'o', 'e', 'h', 'l') ('l', 'o', 'e', 'l', 'h') ('l', 'o', 'l', 'h', 'e') ('l', 'o', 'l', 'e', 'h') ('o', 'h', 'e', 'l', 'l') ('o', 'h', 'e', 'l', 'l') ('o', 'h', 'l', 'e', 'l') ('o', 'h', 'l', 'l', 'e') ('o', 'h', 'l', 'e', 'l') ('o', 'h', 'l', 'l', 'e') ('o', 'e', 'h', 'l', 'l') ('o', 'e', 'h', 'l', 'l') ('o', 'e', 'l', 'h', 'l') ('o', 'e', 'l', 'l', 'h') ('o', 'e', 'l', 'h', 'l') ('o', 'e', 'l', 'l', 'h') ('o', 'l', 'h', 'e', 'l') ('o', 'l', 'h', 'l', 'e') ('o', 'l', 'e', 'h', 'l') ('o', 'l', 'e', 'l', 'h') ('o', 'l', 'l', 'h', 'e') ('o', 'l', 'l', 'e', 'h') ('o', 'l', 'h', 'e', 'l') ('o', 'l', 'h', 'l', 'e') ('o', 'l', 'e', 'h', 'l') ('o', 'l', 'e', 'l', 'h') ('o', 'l', 'l', 'h', 'e') ('o', 'l', 'l', 'e', 'h')
len(list(permutations("hello")))
120
# В предыдущем списке были повторы из-за повторяющейся буквы l
# Контейнер set позволяет от них избавиться
len(set(permutations("hello")))
60
# Следующая функция - itertools.combinations
# Это сочетания из k элементов
for comb in combinations("abcd", 2):
print(comb)
('a', 'b') ('a', 'c') ('a', 'd') ('b', 'c') ('b', 'd') ('c', 'd')
for comb in combinations("dcba", 3):
print(comb)
('d', 'c', 'b') ('d', 'c', 'a') ('d', 'b', 'a') ('c', 'b', 'a')
# Сочетания с повторениями
for comb in combinations_with_replacement("abcd", 3):
print(comb)
('a', 'a', 'a') ('a', 'a', 'b') ('a', 'a', 'c') ('a', 'a', 'd') ('a', 'b', 'b') ('a', 'b', 'c') ('a', 'b', 'd') ('a', 'c', 'c') ('a', 'c', 'd') ('a', 'd', 'd') ('b', 'b', 'b') ('b', 'b', 'c') ('b', 'b', 'd') ('b', 'c', 'c') ('b', 'c', 'd') ('b', 'd', 'd') ('c', 'c', 'c') ('c', 'c', 'd') ('c', 'd', 'd') ('d', 'd', 'd')
# Что еще есть в модуле itertools?
dir(itertools)
['__doc__', '__loader__', '__name__', '__package__', '__spec__', '_grouper', '_tee', '_tee_dataobject', 'accumulate', 'chain', 'combinations', 'combinations_with_replacement', 'compress', 'count', 'cycle', 'dropwhile', 'filterfalse', 'groupby', 'islice', 'permutations', 'product', 'repeat', 'starmap', 'takewhile', 'tee', 'zip_longest']
# Обратите внимание, что имена с подчеркиваниями - скрытые или зарезервированные
# Функция itertools.product - декартово произведение
for elem in product([1,2,3], "ab"):
print(elem)
(1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b')
for number in [1,2,3]:
for letter in "ab":
print(number, letter)
1 a 1 b 2 a 2 b 3 a 3 b
l = [[1,2,3], "abc", [3.14, 2.718], "hello"]
# Декартово перемножить списки внутри нашего l можно с помощью звездочки:
for elem in product(*l):
print(elem)
(1, 'a', 3.14, 'h') (1, 'a', 3.14, 'e') (1, 'a', 3.14, 'l') (1, 'a', 3.14, 'l') (1, 'a', 3.14, 'o') (1, 'a', 2.718, 'h') (1, 'a', 2.718, 'e') (1, 'a', 2.718, 'l') (1, 'a', 2.718, 'l') (1, 'a', 2.718, 'o') (1, 'b', 3.14, 'h') (1, 'b', 3.14, 'e') (1, 'b', 3.14, 'l') (1, 'b', 3.14, 'l') (1, 'b', 3.14, 'o') (1, 'b', 2.718, 'h') (1, 'b', 2.718, 'e') (1, 'b', 2.718, 'l') (1, 'b', 2.718, 'l') (1, 'b', 2.718, 'o') (1, 'c', 3.14, 'h') (1, 'c', 3.14, 'e') (1, 'c', 3.14, 'l') (1, 'c', 3.14, 'l') (1, 'c', 3.14, 'o') (1, 'c', 2.718, 'h') (1, 'c', 2.718, 'e') (1, 'c', 2.718, 'l') (1, 'c', 2.718, 'l') (1, 'c', 2.718, 'o') (2, 'a', 3.14, 'h') (2, 'a', 3.14, 'e') (2, 'a', 3.14, 'l') (2, 'a', 3.14, 'l') (2, 'a', 3.14, 'o') (2, 'a', 2.718, 'h') (2, 'a', 2.718, 'e') (2, 'a', 2.718, 'l') (2, 'a', 2.718, 'l') (2, 'a', 2.718, 'o') (2, 'b', 3.14, 'h') (2, 'b', 3.14, 'e') (2, 'b', 3.14, 'l') (2, 'b', 3.14, 'l') (2, 'b', 3.14, 'o') (2, 'b', 2.718, 'h') (2, 'b', 2.718, 'e') (2, 'b', 2.718, 'l') (2, 'b', 2.718, 'l') (2, 'b', 2.718, 'o') (2, 'c', 3.14, 'h') (2, 'c', 3.14, 'e') (2, 'c', 3.14, 'l') (2, 'c', 3.14, 'l') (2, 'c', 3.14, 'o') (2, 'c', 2.718, 'h') (2, 'c', 2.718, 'e') (2, 'c', 2.718, 'l') (2, 'c', 2.718, 'l') (2, 'c', 2.718, 'o') (3, 'a', 3.14, 'h') (3, 'a', 3.14, 'e') (3, 'a', 3.14, 'l') (3, 'a', 3.14, 'l') (3, 'a', 3.14, 'o') (3, 'a', 2.718, 'h') (3, 'a', 2.718, 'e') (3, 'a', 2.718, 'l') (3, 'a', 2.718, 'l') (3, 'a', 2.718, 'o') (3, 'b', 3.14, 'h') (3, 'b', 3.14, 'e') (3, 'b', 3.14, 'l') (3, 'b', 3.14, 'l') (3, 'b', 3.14, 'o') (3, 'b', 2.718, 'h') (3, 'b', 2.718, 'e') (3, 'b', 2.718, 'l') (3, 'b', 2.718, 'l') (3, 'b', 2.718, 'o') (3, 'c', 3.14, 'h') (3, 'c', 3.14, 'e') (3, 'c', 3.14, 'l') (3, 'c', 3.14, 'l') (3, 'c', 3.14, 'o') (3, 'c', 2.718, 'h') (3, 'c', 2.718, 'e') (3, 'c', 2.718, 'l') (3, 'c', 2.718, 'l') (3, 'c', 2.718, 'o')
# Вопрос из зала: что будет, если не поставить звездочку? Вот ответ:
for elem in product(l):
print(elem)
([1, 2, 3],) ('abc',) ([3.14, 2.718],) ('hello',)
dir(itertools)
['__doc__', '__loader__', '__name__', '__package__', '__spec__', '_grouper', '_tee', '_tee_dataobject', 'accumulate', 'chain', 'combinations', 'combinations_with_replacement', 'compress', 'count', 'cycle', 'dropwhile', 'filterfalse', 'groupby', 'islice', 'permutations', 'product', 'repeat', 'starmap', 'takewhile', 'tee', 'zip_longest']
# Функция itertools.cycle позволяет бесконечно перебирать элементы по кругу
# Мы в этом примере воспользуемся enumerate, чтобы цикл стал конечным
for i, elem in enumerate(cycle("abc")):
if i > 20:
break
print(i, elem)
0 a 1 b 2 c 3 a 4 b 5 c 6 a 7 b 8 c 9 a 10 b 11 c 12 a 13 b 14 c 15 a 16 b 17 c 18 a 19 b 20 c
# Теперь поговорим о генераторах
# Их можно писать как обычные функции, но с оператором yield вместо return
# Вот такой генератор будет строить первые n членов арифметической прогрессии
def progression(a, d, n):
x = a
i = 1
while i <= n:
yield x
x += d
i += 1
for elem in progression(2, 3, 10):
print(elem)
2 5 8 11 14 17 20 23 26 29
g = progression(2, 3, 10)
g
<generator object progression at 0x7f30585702d0>
dir(g)
['__class__', '__del__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__iter__', '__le__', '__lt__', '__name__', '__ne__', '__new__', '__next__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'close', 'gi_code', 'gi_frame', 'gi_running', 'send', 'throw']
# На самом деле там внутри есть метод __next__, который неявно вызывается в цикле for
g.__next__()
2
g.__next__()
5
g.__next__()
8
g.__next__()
11
g.__next__()
14
g.__next__()
17
g.__next__()
20
g.__next__()
23
g.__next__()
26
g.__next__()
29
# На одиннадцатом шаге происходит исключение StopIteration (мы же просили 10 членов!)
g.__next__()
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-54-60e4a84be5d7> in <module>() ----> 1 g.__next__() StopIteration:
# Генератор чисел Фибоначчи (где первые два числа - a и b)
def fib(a, b, n):
i = 1
while i <= n:
yield a
a, b = b, a + b
i += 1
for elem in fib(1, 1, 10):
print(elem)
1 1 2 3
# А вот так можно было бы решить задачу F из контеста про циклы
# (про последовательность натуральных чисел, где каждое число i повторяется i раз)
# Только учтите, что yield from работает начиная с версии 3.3, а в Контесте - 3.2
def sequence():
i = 1
while True:
yield from [i] * i
i += 1
# Вот другое решение той же задачи
def sequence():
i = 1
while True:
for j in in range(i):
yield i
i += 1
for i, elem in enumerate(sequence()):
print(elem)
if i >= 5 - 1:
break
1 2 2 3 3
# Вспомним, как мы подсчитывали буквы в строке
s = "Студенты Высшей школы экономики"
letters = {}
for c in s:
letters[c] = letters.get(c, 0) + 1
# В модуле collections есть удобный класс Counter,
# который уже знает, что 0 - это значение по умолчанию
import collections
s = "Студенты Высшей школы экономики"
letters = collections.Counter()
for c in s:
letters[c] += 1 # не надо думать о том, есть ли такой ключ в словаре
# К тому же, Counter сразу выдает элементы в порядке убывания частоты
print(letters)
Counter({' ': 3, 'к': 3, 'о': 3, 'ы': 3, 'е': 2, 'т': 2, 'ш': 2, 'н': 2, 'и': 2, 'д': 1, 'э': 1, 'м': 1, 'й': 1, 'л': 1, 'у': 1, 'В': 1, 'С': 1, 'с': 1})
# collections.defaultdict - более общая конструкция: словарь со значением по умолчанию
# Counter похож на defaultdict(int)
# В этом искусственном примере мы сопоставляем словам множества их букв
import collections
s = "Студенты Высшей школы экономики"
letters = collections.defaultdict(set)
for word in s.split(" "):
for c in word:
letters[word].add(c)
print(letters)
defaultdict(<class 'set'>, {'школы': {'ш', 'к', 'о', 'ы', 'л'}, 'Студенты': {'д', 'е', 'т', 'н', 'ы', 'у', 'С'}, 'Высшей': {'е', 'ш', 'й', 'ы', 'В', 'с'}, 'экономики': {'э', 'н', 'и', 'к', 'м', 'о'}})
dir(collections)
['ByteString', 'Callable', 'ChainMap', 'Container', 'Counter', 'Hashable', 'ItemsView', 'Iterable', 'Iterator', 'KeysView', 'Mapping', 'MappingView', 'MutableMapping', 'MutableSequence', 'MutableSet', 'OrderedDict', 'Sequence', 'Set', 'Sized', 'UserDict', 'UserList', 'UserString', 'ValuesView', '_Link', '__all__', '__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__path__', '__spec__', '_chain', '_class_template', '_collections_abc', '_count_elements', '_eq', '_field_template', '_heapq', '_iskeyword', '_itemgetter', '_proxy', '_recursive_repr', '_repeat', '_repr_template', '_starmap', '_sys', 'abc', 'defaultdict', 'deque', 'namedtuple']
# Вопрос из зала про queue
import queue
dir(queue)
['Empty', 'Full', 'LifoQueue', 'PriorityQueue', 'Queue', '__all__', '__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'deque', 'heappop', 'heappush', 'threading', 'time']
# Вопрос из зала про range
type(range(100))
range
list(range(100))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
list(range(6))
[0, 1, 2, 3, 4, 5]
# Вот как можно было бы реализовать генератор range (с одним аргументом)
def range(n):
i = 0
while i < n:
yield i
i += 1
for c in range(10):
print(c)
0 1 2 3 4 5 6 7 8 9