сколько способов рассадить — комбинаторика на питоне, путаюсь в перестановках и сочетаниях
Задали по информатике посчитать комбинаторику, а я вообще не понимаю когда что использовать. Есть 5 человек, надо узнать сколькими способами их можно рассадить (это вроде перестановки?) и сколькими способами выбрать из них 2 дежурных (а это сочетания?). Пробовал так:
n = 5
print(n * n * n * n * n) # рассадить
Но это явно неправильно, у меня получается какое-то огромное число. Где я туплю?
2 ответа
Смотри, у тебя там не та формула. Если рассаживаешь всех 5 человек по местам — это перестановки, и считается через факториал n!, а не n в степени n. А «выбрать 2 дежурных из 5, без разницы кто первый» — это сочетания.
В Python всё это уже готовое есть в модуле math:
import math
n = 5
print(math.factorial(n)) # перестановки: 5! = 120
print(math.comb(n, 2)) # сочетания C(5,2) = 10
print(math.perm(n, 2)) # размещения A(5,2) = 20
Как это запомнить простыми словами:
- Перестановки — рассадить всех, порядок важен →
n! - Размещения (
math.perm) — выбрать k из n, порядок важен (например распределить медали золото/серебро/бронза) - Сочетания (
math.comb) — выбрать k из n, порядок НЕ важен (просто группа дежурных)
Главное отличие сочетаний от размещений: важен ли порядок. Дежурные Петя+Вася = Вася+Петя, поэтому сочетания. А золото Пете и серебро Васе — это уже другой расклад, поэтому размещения.
Если вдруг нужно без math.comb (на старом питоне или просто чтоб понять формулу), сочетания можно руками:
import math
def c(n, k):
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
print(c(5, 2)) # 10
Формула C(n,k) = n! / (k! * (n-k)!). Деление целочисленное //, потому что ответ всегда целый.
