Комбинаторика (2)

1. Python: генератор списков

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
1
Python: генератор списков
• создать новый массив
A = [ x for x in range(100) ]
from random import randint
A = [ randint(10,100)
for x in range(100) ]
• с фильтрацией
A = [ x for x in range(100)
if x % 7 == 0 ]
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

2. Python: генератор списков

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
2
Python: генератор списков
• преобразовать элементы массива (map)
A = [ x*x for x in A ]
• построить массив из элементов другого
массива, удовлетворяющих условию (filter)
B = [ x for x in A if x % 2 == 0 ]
• совмещение (map + filter)
B = [ x*x for x in A
if x % 2 == 0 ]
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

3. Python: all, any

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
3
Python: all, any
• all – истинно для всех
if all( x > 0 for x in A ):
print( "Все > 0" )
• any – истинно хотя бы для одного
if any( x > 0 for x in A ):
print( "Есть какой-то > 0" )
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

4. Python: product

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
4
Python: product
Декартово произведение: «каждый с каждым»
from itertools import product
for w in product( A, B ):
print( w )
(1, 'A')
(1, 'B')
(2, 'A')
(2, 'B')
(3, 'A')
(3, 'B')
for w in product(B, repeat=2 ):
print( w )
# print( ''.join(w) )
# -> ["AA", "AB", "BA", "BB"]
('A', 'A')
('A', 'B')
('B', 'A')
('B', 'B')
A = [1, 2, 3]
B = ['A','B']
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

5. Python: product – генератор (на 1 раз)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
5
Python: product – генератор (на 1 раз)
from itertools import product
A = [1, 2, 3]
B = ['A','B']
P = product(A, B)
print( P )
(1, 'A')
(1, 'B')
'A')
<itertools.product (2,
object
at 0x33EF7C0>
(2, 'B')
for w in P:
(3, 'A')
print( w )
(3, 'B')
for w in P:
пусто
print( w )
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

6. Python: permutations – перестановки

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
6
Python: permutations – перестановки
from itertools import permutations
A = [1, 2, 3]
for p in permutations(A):
print( p )
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1)
(3, 1, 2) (3, 2, 1)
Размещения:
for p in permutations(A, 2):
print( p )
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

7. Python: combinations – сочетания

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
7
Python: combinations – сочетания
from itertools import combinations
A = [1, 2, 3, 4]
for p in combinations(A, 4):
print( p )
(1, 2, 3, 4)
for p in combinations(A, 2):
print( p )
(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

8. Python: zip

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
8
Python: zip
Соединение двух (n?) массивов в пары (кортежи):
A = [1, 2, 3, 4, 5]
B = ['A','B','C','D','E']
1,2,3,4,5
zip
(1,A),(2,B),(3,C)...
A,B,C,D,E
for p in zip(A, B):
print( p, end=" " )
(1, 'A') (2, 'B') (3, 'C') (4, 'D')
(5, 'E')
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

9. Python: zip

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
9
Python: zip
Соединение двух массивов в пары:
A = [1, 2, 3, 4, 5]
B = ['A','B','C','D','E']
for a,
a, bb in zip(A, B):
print( a, b )
1 A
2 B
3 C
4 D
5 E
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

10. Новые возможности PascalABC.NET и Python при решении задач ЕГЭ

Комбинаторика
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

11. 8. Список слов

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
11
8. Список слов
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
буквы Н и К встречаются ровно по два раза?
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

12. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
12
8. Список слов (Python)
from itertools import product
allWords = product('ВЕНОК', repeat=5)
Можно не
# [('В', 'В', 'В', 'В', 'В'),
строить
# ('В', 'В', 'В', 'В', 'Е'), ... ]
строки
words = [ w for w in allWords
if w.count('Н') == 2 and
w.count('К') == 2 ]
print( len(words) )
90
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

13. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
13
8. Список слов (Python)
from itertools import product
words = [ w
for w in product('ВЕНОК', repeat=5)
if w.count('Н') == 2 and
w.count('К') == 2 ]
print( len(words) )
90
К.Ю. Поляков, 2023
cписок, все
данные в
памяти
http://kpolyakov.spb.ru

14. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
14
8. Список слов (Python)
from itertools import product
ones = ( 1
for w in product('ВЕНОК', repeat=5)
if w.count('Н') == 2 and
w.count('К') == 2 )
print( sum(ones) )
90
К.Ю. Поляков, 2023
генератор, в
памяти только
одно текущее
значение
http://kpolyakov.spb.ru

15. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
15
8. Список слов (Python)
from itertools import product
print( sum( 1
for w in product('ВЕНОК', repeat=5)
if w.count('Н') == 2 and
w.count('К') == 2 ) )
90
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

16. 8. Список слов

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
16
8. Список слов
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
встречается сочетание букв «НК»?
Важно: нужно проверить сочетание символов
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

17. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
17
8. Список слов (Python)
from itertools import product
allWords = product('ВЕНОК', repeat=5)
# [('В', 'В', 'В', 'В', 'В'),
# ('В', 'В', 'В', 'В', 'Е'), ... ]
strWords = [ ''.join(x)
for x in allWords ]
words = [ w for w in strWords
if 'НК' in w ]
'ВВВВВ'
'ВВВВЕ'
...
print( len(words) )
485
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

18. 8. Список слов (Python, кратко)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
18
8. Список слов (Python, кратко)
from itertools import product
allWords = [ ''.join(w)
''.join(w) for w in
product('ВЕНОК', repeat=5) ]
words = [ w for w in allWords
if 'НК' in w ]
print( len(words) )
485
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

19. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
19
8. Список слов (Python)
from itertools import product
ones = ( 1
for w in product('ВЕНОК', repeat=5)
if 'НК' in ''.join(w)
''.join(w) )
print( sum(ones) )
485
К.Ю. Поляков, 2023
Генератор,
экономия
памяти
http://kpolyakov.spb.ru

20. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
20
8. Список слов (Python)
from itertools import product
логическое
print( sum(
значение
'НК'
in
''.join(w)
'НК'
''.join(w)
for w in product('ВЕНОК', repeat=5)))
485
К.Ю. Поляков, 2023
!
False 0, True 1!
http://kpolyakov.spb.ru

21. 8. Список слов

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
21
8. Список слов
(А.Н. Носкин) Все пятибуквенные слова, составленные из
букв В, Е, Н, О, К, записаны в алфавитном порядке и
пронумерованы, начиная с 1. Начало списка выглядит
так:
1. ВВВВВ
2. ВВВВЕ
3. ВВВВК
4. ВВВВН
5. ВВВВО
6. ВВВЕВ
...
Под каким номером в списке идёт последнее слово, в
котором буквы Н и К встречаются ровно по два раза?
Важно: 1) алфавитный порядок
2) нужен номер слова
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

22. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
22
8. Список слов (Python)
from itertools import product Сортировка
allWords = product(
sorted('ВЕНОК'), repeat=5)
allPairs = [ (n+1, w) # добавляем номер
for n, w in enumerate(allWords) ]
pairs = [ p for p in allPairs
if p[1].count('Н') == 2 and
p[1].count('К') == 2 ]
print( pairs[-1] ) # последняя пара
(2963,('О','Н','Н','К','К'))
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

23. 8. Список слов (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
23
8. Список слов (Python)
from itertools import product
print( [ (n+1, w)
for n, w in enumerate(
product(sorted('ВЕНОК'), repeat=5))
if w.count('Н') == 2 and
w.count('К') == 2 ][-1] ) последний
элемент
(2963,('О','Н','Н','К','К'))
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

24. 8. Перестановки

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
24
8. Перестановки
Маша составляет 5-буквенные коды из букв
В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1
раз, при этом буква Ь не может стоять на первом месте.
Сколько различных кодов может составить Маша?
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

25. 8. Перестановки (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
25
8. Перестановки (Python)
Маша составляет 5-буквенные коды из букв
В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1
раз, при этом буква Ь не может стоять на первом месте.
Сколько различных кодов может составить Маша?
from itertools import permutations
words = [ w for w in permutations('ВУАЛЬ')
if w[0] != 'Ь' ]
print( len(words) )
96
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

26. 8. Перестановки (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
26
8. Перестановки (Python)
from itertools import permutations
print( sum(
1 for w in permutations('ВУАЛЬ')
if w[0] != 'Ь' ) )
from itertools import permutations
print( sum( w[0] != 'Ь'
for w in permutations('ВУАЛЬ') ) )
96
Автор: А. Богданов
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

27. 8. Перестановки

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
27
8. Перестановки
Маша составляет 5-буквенные коды из букв
В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1
раз, при этом буква Ь не может стоять на первом месте
и перед A. Сколько различных кодов может составить
Маша?
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

28. 8. Перестановки (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
28
8. Перестановки (Python)
from itertools import permutations
print( len( [
w for w in permutations('ВУАЛЬ')
if w[0] != 'Ь' and
'ЬА' not in ''.join(w) ] ) )
78
print( sum(
11 for w in permutations('ВУАЛЬ')
if w[0] != 'Ь' and
'ЬА' not in ''.join(w) ) )
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

29. 8. Перестановки

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
29
8. Перестановки
(А.Н. Носкин) Петя составляет семибуквенные
слова перестановкой букв слова АССАСИН.
Сколько всего различных слов может составить
Петя?
одинаковые буквы в
слове при «тупом»
В
чём
подвох?
?
переборе дадут
дубли
!
К.Ю. Поляков, 2023
Избавляемся
от дублей!
http://kpolyakov.spb.ru

30. Решение «АССАСИН»

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
30
Решение «АССАСИН»
.Distinct
420
К.Ю. Поляков, 2023
! Неверный ответ!
http://kpolyakov.spb.ru

31. Решение «АССАСИН» (HashSet)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
31
Решение «АССАСИН» (HashSet)
##
'АССАСИН'.Permutations.ToHashSet
.Count
.Println
Множество на
основе хэштаблицы
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

32. Решение «АССАСИН» (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
32
Решение «АССАСИН» (Python)
from itertools import permutations
print( len(
set ( permutations('АССАСИН') ) ) )
420
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

33. 8. Перестановки

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
33
8. Перестановки
Артур составляет 5-буквенные коды
перестановкой букв слова АРЕАЛ. При этом
нельзя ставить рядом две гласные. Сколько
различных кодов может составить Артур?
Важно: 1) одинаковые буквы (дубли!)
2) нужно строить строки
3) рассматриваются
пары соседних букв
.Pairwise
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

34. Решение «АРЕАЛ» (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
34
Решение «АРЕАЛ» (Python)
from itertools import permutations
allWords = set( permutations('АРЕАЛ') )
или ()
# { (А,Р,Е,А,Л),
#
(А,Р,Е,Л,А) ... }
pairsArr = [ zip(w, w[1:]) for w in allWords ]
# [ [(А,Р),(Р,Е),(Е,А),(А,Л)],
#
[(А,Р),(Р,Е),(Е,Л),(Л,А)] ...
valid = [ pairs for pairs in pairsArr
if all( p[0]+p[1] not in 'ААЕЕА'
for p in pairs ) ]
print( len(valid) )
6
w: (А,Р,Е,А,Л)
zip
w[1:]: (Р,Е,А,Л)
К.Ю. Поляков, 2023
только []
[(А,Р),(Р,Е),
(Е,А),(А,Л)]
http://kpolyakov.spb.ru

35. Решение «АРЕАЛ» (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
35
Решение «АРЕАЛ» (Python)
from itertools import permutations
pairsArr = (( zip(w, w[1:])
for w in set( permutations('АРЕАЛ') ) ))
print( sum( 1 for pairs in pairsArr
if all( p[0]+p[1] not in 'ААЕЕА'
for p in pairs ) ) )
6
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

36. 8. Комбинации

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
36
8. Комбинации
Сколько шестнадцатеричных кодов чисел длиной
12 можно составить, если известно, что цифры
идут в порядке убывания, при этом четные и
нечетные цифры чередуются.
Важно: 1) строить все 12-значные числа долго!
2) все цифры в числе разные
(комбинации!)
3) рассматриваются
пары соседних цифр
.Pairwise
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

37. Решение «HEX-коды» (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
37
Решение «HEX-коды» (Python)
from itertools import combinations
allNums = combinations( 'GFEDCB9876543210', 12 )
# [(G,F,E,D,C,B,9,8,7,6,5,4),
# (G,F,E,D,C,B,9,8,7,6,5,3), ... ]
valid = [ n for n in allNums
if all( (ord(p[0])-ord(p[1])) % 2 == 1
for p in zip(n,n[1:]) ) ]
print( len(valid) )
104
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru

38. Решение «HEX-коды» с числами (Python)

Новые возможности PascalABC.NET и Python для решения задач ЕГЭ
38
Решение «HEX-коды» с числами (Python)
from itertools import combinations
allNums = combinations( range(16)
range(16), 12 );
ones = ( 1 for n in allNums
if all( (p[0]-p[1]) % 2 == 1
for p in zip(n,n[1:]) ) )
print( sum(ones) )
104
К.Ю. Поляков, 2023
http://kpolyakov.spb.ru