Product 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 модуле itertools существует
ряд комбинаторных функций. Рассмотрим некоторые из них:

· product() –
прямое произведение одного или нескольких итераторов.

· permutations() –
перестановки и размещения элементов множества.

Данная библиотека позволяет
решать задачи с комбинаторикой, упрощая программу решения.

Вызов модуля itertools:

from itertools import *

Данный модуль можно
использовать для решения задач №8 ЕГЭ по информатике.

Примеры заданий и способы
использования данного модуля.

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

Аналитический способ решения

Общее количество слов с
учетом, что в слове две буквы «А» (перестановка этих букв не дает нового слова)

Вычтем количество слов,
начинающихся с гласной с учетом 2 букв «А»:

Получаем =180 слов

Итого: 360 – 180 = 180

Программа для решения данной
задачи:

from itertools import *

a=’МАРИНА‘

k=0

for i in set(permutations(a)):

    s=».join(i)

    if s[0] not in ‘АИ‘:

        k+=1

print(k)

В программе
используем

1)    функцию: 
permutations(a), т.к. слова составляются
перестановкой букв;

2)   
используем множества (set), чтобы слова не повторялись;

3)    в условии проверяем отсутствие гласных  в начале слова.

Пример 2. Используем функцию product

Миша составляет
5-буквенные коды из букв К, А, Л, Ь, К, А. Каждая допустимая гласная буква
может входить в код не более одного раза. Сколько кодов может составить Миша?

Аналитический способ решения

Количество слов без «А»

3*3*3*3*3= 3⁵ =243

Количество слов с одной  «А»

5 вариантов *3*3*3*3 = 405

Итого: 243 + 405 = 648

Программа для решения данной
задачи:

from itertools import*

a=’КАЛЬ’

k=0

for i in product(a, repeat=5):

    s=».join(i)

    if s.count(‘А’)<=1 :

        k+=1                               

print (k)

В программе
используем

1)    функцию
product (a, repeat=5):
, т.к. буквы в слове могут повторяться;

2)    в условии проверяем количество гласных  не более 1.

Для решения задачи (25) полезно уметь пользоваться (f)-строками — форматированными выражениями, содержащими поля замены. Форматированные (f)-строки имеют вид f'<текст >{объект}< текст>’. Поля замены ограничиваются фигурными скобками, и значения в них подставляются во время выполнения программы.

Например, фрагменты программ:

print(‘Решать задания ЕГЭ мне помогают материалы ЯКласс!’)

print(f’Решать задания ЕГЭ мне помогают материалы ЯКласс!’)

будут выполняться одинаково, хотя в верхней строке обычное форматирование, а во второй — (f)-строка. Обратим на это внимание в следующем примере.

Рис. (1). Пример вывода

Рис. (2). Результат работы программы (1)

Для аккуратного форматирования придётся воспользоваться разделителем sep(=»)  и вставкой дополнительных пробелов в текст для того, чтобы избавиться от автоматически расставляемых пробелов на месте запятых в функции print.

Сравни результат работы с результатом работы (f)-строки:

Рис. (3). Пример вывода (f)-строки

Рис. (4). Результат работы программы (2)

Конечно, этим не исчерпываются возможности (f)-строк.

Рассмотрим задачу на поиск делителей числа. 

Пример (1)

Для некоторого случайного числа в интервале ([4,12300]) подсчитай количество нетривиальных делителей и выведи их.

Решение

Рис. (5). Программа (1)

Рис. (6). Результат работы программы (3)

Обрати внимание на оформление вывода. Результаты работы программы форматированы как (f)-строки. В качестве объекта в фигурных скобках записана стандартная функция len от другой функции mult. Одна из этих функций составлена пользователем и описана здесь же в программе. Кроме использования вычислений в (f)-строке мы также можем форматировать нужные нам строки.

Пример (2)

Даны символы «e», «c», «t», «f», «j», «k», «y». Сколько различных имён файлов, соответствующих маске (1?23.?x?), можно составить из предложенных символов? Сколько из них будут иметь расширение «txt» или «exe»?

Рис. (7). Программа (2)

Обрати внимание: для контроля за работой программы мы вывели на печать имена файлов с заданными расширениями.

Рис. (8). Результат работы программы (4)

Разбор досрочного варианта (2022)

Назовём маской числа последовательность цифр в которой также могут встречаться следующие символы:

• символ «?» означает ровно одну произвольную цифру;

• символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Среди натуральных чисел, не превышающих (10**9), найди все числа, соответствующие маске (12345?6?8) и делящиеся на (17) без остатка.

В ответе запиши в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им частные от деления на (17).

Здесь полем замены будут цифры, занимающие места «?».

Рис. (9). Программа (3)

Рис. (10). Результат работы программы (5)

Для решения задач с применением масок числа полезно знать работу функции product модуля itertools.

В условии задачи досрочного варианта упоминается, что в маске может находиться «*», а это набор символов любой длины, в том числе и нулевой.

Функция product модуля itertools сформирует нам необходимую комбинацию символов для замены «*».

Рассмотрим пример её работы.

Пример (3)

Составь все возможные пары из элементов строк (‘0123’) и (‘abcd’) — такие, чтобы первый элемент был из числовой строки, а следующий — из текстовой. (Множество таких пар элементов называется декартовым произведением первой и второй из заданных строк.)

Рис. (11). Программа (4)

Мы получили список, состоящий из кортежей, первый элемент которых — из числовой строки, а второй — из текстовой.

Рис. (12). Результат работы программы (6)

Но для вставки вместо «*» нам нужно преобразовать кортежи, из которых состоит список, в строки.

Пример (3A)

Метод  join преобразовал кортежи в строки.

Рис. (13). Результат работы программы (7)

Если необходимо составить комбинации пар, или троек, или иного количества символов одного множества, то необходимо задать параметр repeat для функции product.

Пример (3B)

Составь таблицу истинности логической функции

((x→y)≡(z→w))∨(x∧w).

Рис. (14). Программа (5)

Рис. (15). Результат работы программы (8)

Пример (3C)

Рис. (16). Программа (6)

Рис. (17). Результат работы программы (9)

Вот эти строки уже можно вставлять на место «*».

Рассмотрим ещё одно задание из ЕГЭ прошлых лет.

Пример (4)

Определи, какое из указанных имён файлов удовлетворяет маске (‘?vi*r.?xt’).

1) vir.txt 

2) ovir.txt

3) ovir.xt

4) virr.txt

Задание решалось вручную, и мы можем составить программу и сопоставить ответ, полученный программой, с ручными расчётами.

Рис. (18). Программа (7)

Информация о материале

Опубликовано: 01 декабря 2021

Просмотров: 426

alphabet = "ТИМАШЕВСК"
words = [''.join(iword) for iword in itertools.product(alphabet, repeat=6)]
# 6-ти-буквенные слова в списке из любого набора букв

from itertools import *

word = 'СПОРТЛОТО'
i = 0
for w in permutations(word):
    print(''.join(w))
    i += 1
    if i > 2:
        break
i = 0
for w in product(word, repeat=4):
    print(''.join(w))
    i += 1
    if i > 10:
        break

from itertools import *

w = 3
for px in product('0123456', repeat=w):
    print(int(''.join(px)))

def anySS_count_print(ss, w):
    sdigits = ''.join([str(x) for x in range(ss)])
    for px in product(sdigits, repeat=w):
        r = str(int(''.join(px)))
        print(r)
    
anySS_count_print(7, 3)

from functools import *

@lru_cache(None)

def f(n):
    if n == 0:
        return 0
    elif 1 <= n < 3:
        return 1
    elif n >= 3:
        return f(n - 1) + f(n - 2)
    
print(f(47))

def toSS(n, ss):
    res = ''
    while n > 0:
        d = str(n % ss)
        res = d + res
        n //= ss
    return res
    
n7 = 234532
s7 = toSS(n7, 7)
print(n7, s7)
print(int(s7, 7))

import itertools

itertools.product(*iterables, repeat=1)

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

>>> from itertools import product
>>> x = ['a', 'b', 'c']
>>> y = ['1', '2']
>>> list(product(x, y))
# [('a', '1'), ('a', '2'), ('b', '1'), ('b', '2'), ('c', '1'), ('c', '2')]

>>> list(product(y, repeat=3))
# [('1', '1', '1'), ('1', '1', '2'), ('1', '2', '1'), ('1', '2', '2'), 
# ('2', '1', '1'), ('2', '1', '2'), ('2', '2', '1'), ('2', '2', '2')]

>>> list(product(x, y, repeat=2))
# [('a', '1', 'a', '1'), ('a', '1', 'a', '2'), ('a', '1', 'b', '1'), ('a', '1', 'b', '2'), 
# ('a', '1', 'c', '1'), ('a', '1', 'c', '2'), ('a', '2', 'a', '1'), ('a', '2', 'a', '2'), 
# ('a', '2', 'b', '1'), ('a', '2', 'b', '2'), ('a', '2', 'c', '1'), ('a', '2', 'c', '2'), 
# ('b', '1', 'a', '1'), ('b', '1', 'a', '2'), ('b', '1', 'b', '1'), ('b', '1', 'b', '2'), 
# ('b', '1', 'c', '1'), ('b', '1', 'c', '2'), ('b', '2', 'a', '1'), ('b', '2', 'a', '2'), 
# ('b', '2', 'b', '1'), ('b', '2', 'b', '2'), ('b', '2', 'c', '1'), ('b', '2', 'c', '2'), 
# ('c', '1', 'a', '1'), ('c', '1', 'a', '2'), ('c', '1', 'b', '1'), ('c', '1', 'b', '2'), 
# ('c', '1', 'c', '1'), ('c', '1', 'c', '2'), ('c', '2', 'a', '1'), ('c', '2', 'a', '2'), 
# ('c', '2', 'b', '1'), ('c', '2', 'b', '2'), ('c', '2', 'c', '1'), ('c', '2', 'c', '2')]

Problem 

itertools.product()

This tool computes the cartesian product of input iterables.

It is equivalent to nested for-loops.

For example, product(A, B) returns the same as ((x,y) for x in A for y in B).

Sample Code

>>> from itertools import product
>>>
>>> print list(product([1,2,3],repeat = 2))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
>>>
>>> print list(product([1,2,3],[3,4]))
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)]
>>>
>>> A = [[1,2,3],[3,4,5]]
>>> print list(product(*A))
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)]
>>>
>>> B = [[1,2,3],[3,4,5],[7,8]]
>>> print list(product(*B))
[(1, 3, 7), (1, 3, 8), (1, 4, 7), (1, 4, 8), (1, 5, 7), (1, 5, 8), (2, 3, 7), (2, 3, 8), (2, 4, 7), (2, 4, 8), (2, 5, 7), (2, 5, 8), (3, 3, 7), (3, 3, 8), (3, 4, 7), (3, 4, 8), (3, 5, 7), (3, 5, 8)]

---

Task

You are given a two lists A and B. Your task is to compute their cartesian product AXB.

---

Example

A = [1, 2]
B = [3, 4]

AxB = [(1, 3), (1, 4), (2, 3), (2, 4)]

Note: A and B are sorted lists, and the cartesian product’s tuples should be output in sorted order.

---

Input Format

The first line contains the space separated elements of list A.

The second line contains the space separated elements of list B.

Both lists have no duplicate integer elements.

---

Output Format

Output the space separated tuples of the cartesian product.

---

Sample Input

---

Sample Output

 (1, 3) (1, 4) (2, 3) (2, 4)

---

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Enter your code here. Read input from STDIN. Print output to STDOUT

from itertools import product
A = list(map(int,input().split()))
B = list(map(int,input().split()))

result = list(product(A,B))

for i in result:
    print(i,end=" ")