Itertools python егэ

Задание номер 8 — задание базового уровня сложности, выполнение которого предполагает знание о методах измерения количества информации и не требует использования специального ПО.

Зачастую в номере 8 мы можем встретить задания связанные с комбинаторикой — перестановками, количеством вариантов выборки и т.д. Для решения заданий такого типа можно приспособить модуль itertools языка python.

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

Модуль itertools доступен в питоне «из коробки», т.е. его нет необходимости устанавливать дополнительно. А значит, он будет доступен на экзамене.

Ссылка на документацию по модулю https://docs.python.org/3/library/itertools.html

Использованные в данной статье методы и функции доступны как минимум с версии питона 3.6

Для импорта необходимых функции необходимо их импортировать из модуля

from itertools import product, permutations

1. product

Позволяет получить прямое, или декартово произведеение двух множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств.

a = ‘AB’

b = ‘CD’

print(*product(a, b))

(‘A’, ‘C’) (‘A’, ‘D’) (‘B’, ‘C’) (‘B’, ‘D’)

Получение произведения двух множеств не очень актуально в 8 задании, но мы можем использовать другую возможность функции product: получение всевозможных комбинаций определенной длины для одного множества.

a = ‘AB’

print(*product(a, repeat=3))

(‘A’, ‘A’, ‘A’) (‘A’, ‘A’, ‘B’) (‘A’, ‘B’, ‘A’) (‘A’, ‘B’, ‘B’) (‘B’, ‘A’, ‘A’) (‘B’, ‘A’, ‘B’) (‘B’, ‘B’, ‘A’) (‘B’, ‘B’, ‘B’)

Мы получили всевозможные комбинации длины 3 для набора из двух букв АВ. Причем результат работы функции — набор кортежей.

Параметр repeat отвечает за длину слова.

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

Длина слова здесь 3, а набор букв — ШКОЛА. Получим всевозможные комбинации:

a = ‘ШКОЛА’

comb = product(a, repeat=3))

Осталось выбрать те, где буква К встречается ровно 1 раз.

Поскольку подсчет количества вхождений в кортеж организовать сложнее, чем в строке, здесь элементы кортежа «склеиваются» по пустой строке, образуя тем самым не кортеж, а строку. Метод count подсчитывает количество вхождений подстроки ‘K’.

Этот же код можно оформить в одну строку через списочное выражение

print(len([item for item in product(‘ШКОЛА’, repeat=3) if ”.join(item).count(‘К’) == 1]))

2. permutations

Позволяет получить всевозможные перестановки.

print(*permutations(‘ABC’))

(‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)

Это опять набор кортежей.

Рассмотрим такое задание с сайта kpolyakov.spb.ru

Получаем перестановки

a = ‘КАПКАН’

comb = permutations(a)

И отбираем нужные варианты

Поскольку в слове КАПКАН есть повторяющиеся буквы А и К, мы должны поделить итоговое количество на 4 (дважды поделить на 2), поскольку с нашей точки зрения эти комбинации неотличимы друг от друга.

Другой способ убрать повторяющиеся комбинации — превратить набор перестановок в множество, которое в питоне исключает повторы

Так-же можно написать решение в одну строку

print(len([i for i in set(permutations(‘КАПКАН’)) if all(i[j] != i[j + 1] for j in range(5))]))

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

Использование модуля itertools в Python при решении задач на уроках информатики по теме «Комбинаторика».

Очень часто на уроках информатики встречаются задачи перебора различных вариантов последовательностей, состоящих из букв или цифр. Данный класс задач встречается и в Компьютерном ЕГЭ. С 2022 года формат сдачи ЕГЭ изменился и теперь для решения задач можно использовать программные средства и языки программирования. Мы рассмотрим эту возможность решения на языке Python

Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:

Комбинация – это набор элементов, порядок которых не имеет значения.

Перестановка – это расположение набора, в котором порядок имеет значение.

Рассмотрим набор как:{A, B, C}

Перестановки вышеуказанного набора следующие:

 (‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)

Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:

 (‘A’, ‘B’) (‘A’, ‘C’) (‘B’, ‘C’)

В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр. Мы будем использовать методы combinations() и permutations() в модуле itertools.
Перестановки числовых данных. 

Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.

from itertools import *

Теперь давайте определим набор чисел.

val = [1, 2, 3, 4]

Теперь, чтобы получить список перестановок, воспользуемся методом permutations().

perm_set = permutations(val)

Строка кода выше дает объект itertools.

Чтобы напечатать различные перестановки, мы будем перебирать этот объект.

 for i in perm_set:

      print( i,)

Мы получаем результат как кортежи четырех чисел:

(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)-

Полный код этого раздела приведен ниже:

from itertools import *

val = [1, 2, 3, 4]

perm_set = permutations(val)

for i in perm_set:

    print(I, end=’-‘)

Перестановки строки  

Далее мы узнаем, как получить перестановки символов в строке. Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.
from itertools import *

s = «ABC»

perm_set = permutations(s)

for val in perm_set:

      print(val)

Вывод : (‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)

Перестановки фиксированной длины

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

Код для поиска перестановок фиксированной длины приведен ниже:

from itertools import *

val = [1, 2, 3, 4]

perm_set = permutations(val,2)

for i in perm_set:

     print(i)

Вывод : (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

Комбинации числовых данных.

Так же, как метод permutations(), мы можем использовать combinations() для получения комбинаций набора. При вызове combinations() нам нужно передать два аргумента: набор для поиска комбинаций и число, обозначающее длину каждой комбинации.

from itertools import *

val = [1, 2, 3, 4]

com_set = combinations(val, 2)

for i in com_set: print(i)

Вывод : (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

Комбинации строки

Мы также можем получить комбинации строки.

from itertools import *

s = «ABC»

com_set = itertools.combinations(s, 2)

for i in com_set: print(i)

Вывод : (‘A’, ‘B’) (‘A’, ‘C’) (‘B’, ‘C’)

Комбинации с заменами

В модуле itertools есть еще один метод, который называется комбинациями with_replacement(). Этот метод также учитывает комбинацию числа с самим собой. Посмотрим, как это работает.

Для числового набора

from itertools import *

val = [1, 2, 3, 4]

com_set = itertools.combinations_with_replacement(val, 2)

for i in com_set:

print(i)

Вывод : (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

Вы можете видеть разницу в выводе выше и выводе для работы нормальной комбинации. Здесь у нас есть такие комбинации, как (1,1) и (2,2), которых нет в обычных комбинациях.

Для строки

from itertools import *

val = «ABCD»

com_set = combinations_with_replacement(val, 2)

 for i in com_set:

       print(i)

Вывод : (‘A’, ‘A’) (‘A’, ‘B’) (‘A’, ‘C’) (‘A’, ‘D’) (‘B’, ‘B’) (‘B’, ‘C’) (‘B’, ‘D’) (‘C’, ‘C’) (‘C’, ‘D’) (‘D’, ‘D’)

Пример 1

Петя составляет семибуквенные слова перестановкой букв слова ТРАТАТА. Сколько всего различных слов может составить Петя?

from itertools import *

val = ‘ТРАТАТА’

com_set = list(set(permutations(val)))

print(len(com_set))

Так как  в слове ТРАТАТА есть повторяющие буквы Т и А. Создаем множество set в котором убираем одинаковые элементы созданные одинаковыми буквами.

Пример 2

Юрий составляет 4-буквенные слова из букв П, Р, И, К, А, З. Каждую букву можно использовать не более одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов может составить Юрий?

from itertools import *

val = ‘ПРИКАЗ’

com_set = permutations(val, 4)

count = 0

for x in com_set:

    if ‘И’ not in x and ‘А’ in x or ‘А’ not in x and ‘И’ in x or ‘И’ not in x and ‘А’ not in x:

        count += 1

print(count)

Пример 3

Георгий составляет коды из букв своего имени. Код должен состоять из 7 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Георгий?

from itertools import *

k = 0

for x in set(permutations(‘ГЕОРГИЙ’)):

    s = ».join(x)

    if ‘ГГ’ not in s:

        k += 1

print(k)