Лабораторная работа № 11. Решение комбинаторных задач с помощью Python

Теоретические сведения

Алгоритм выбора комбинационной формулы

Вычисление факториала

Для вычисления факториала используем функцию factorial() модуля math:

# импорт функции из модуля math
from math import factorial

# вызов функции
p = factorial(3)

Генерация списка перестановок, размещений и сочетаний

Для получения списка требуемых комбинаций средствами Python, нужно импортировать подходящую функцию из модуля itertools:

permutations(<последовательность>) - генерация перестановок.
permutations(<последовательность>, m) - генерация размещений без повторений по $m$ элементов в каждом.
combinations(<последовательность>, m) - генерация сочетаний без повторений по $m$ элементов в каждом.

Импорт функций:

from itertools import permutations, combinations

Результат работы функции-генератора комбинаций можно преобразовать в список для получения отдельной комбинации по индексу, последовательности комбинаций по срезу:

# в переменной сохранится список перестановок
lst = list(permuations(<последовательность>))

lst[0]      # первый элемент списка
lst[5:11]   # срез списка с пятого по десятый элементы

Каждая сгенерированная комбинация относится к типу данных кортеж. Элементы кортежа можно индексировать так же, как элементы других последовательностей.

comb = lst[0] # первая комбинация
comb[0]     # первый элемент в сгенерированной комбинации
comb[-1]    # последний элемент в сгенерированной комбинации

Чтобы выбрать один случайны элемент из списка, можно использовать функцию choice() из модуля random. Перед использованием функцию нужно импортировать в программу:

from random import choice

choice(lst) # случайный элемент из списка lst

Задания для самостоятельной работы

💻 Задание 1 (sam01.py)

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

По условию необходимо сгенерировать все x размещения без повторений. Например, если количество участников равно 6, и количество призовых мест равно 3, то количество комбинаций равно x .

Составьте код решения задачи из предложенных блоков.