Использование модуля 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)