Як обчислити кількість перестановок n елементів?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Кількість перестановок n різних елементів дорівнює n! (факторіал n). За визначенням n! = 1 · 2 · 3 · … · n, а 0! = 1.

Докладне пояснення

Що таке факторіал

Визначення: n! = 1 · 2 · 3 · … · n для n ≥ 1; за домовленістю 0! = 1.
Рекурентно: n! = n · (n − 1)!, де 0! = 1.
Приклад: 5! = 1 · 2 · 3 · 4 · 5 = 120.

Перестановка - це впорядкування всіх n різних елементів. На перше місце можна поставити будь-який з n елементів, на друге - будь-який із залишку (n − 1), на третє - (n − 2) і так далі, поки не вичерпаємо елементи. Перемножуючи кількість варіантів на кожному кроці, отримуємо n · (n − 1) · (n − 2) · … · 2 · 1 = n!.

Приклади перестановок

n = 3: 3! = 6. Перестановки елементів {A, B, C}: ABC, ACB, BAC, BCA, CAB, CBA.
n = 5: 5! = 120.
n = 0: 0! = 1 (одна «порожня» перестановка).

Часті варіації на співбесідах

Розміщення без повторень (впорядковані вибірки з n по k): A(n, k) = n! / (n − k)!. Приклад: A(5, 2) = 5 · 4 = 20.
Перестановки з повтореннями: якщо серед n елементів є групи, що повторюються, розмірів m1, m2, …, mr (m1 + … + mr = n), то кількість різних перестановок дорівнює n! / (m1! · m2! · … · mr!). Приклад: перестановки слова «ANNA» (літери: A×2, N×2) - 4! / (2! · 2!) = 6.
Кругові перестановки (розташування по колу, де повороти вважаються однаковими): (n − 1)!.
Впорядковані послідовності довжини k з поверненням (вибір із повтореннями): n^k.

Практичні зауваження

Факторіал зростає дуже швидко: вже 20! ≈ 2.43e18, тому використовуйте типи великих чисел (BigInt, arbitrary precision).
Остерігайтеся переповнення стандартних цілочисельних типів.
У багатьох задачах факторіал не обчислюють напряму - використовують скорочення в дробах (наприклад, в A(n, k) скорочують добуток).

Код: як порахувати n! на практиці

JavaScript (BigInt):

function factorial(n) {
  if (!Number.isInteger(n)) throw new TypeError('n must be an integer');
  if (n < 0) throw new RangeError('n must be >= 0');
  let result = 1n;
  const N = BigInt(n);
  for (let i = 2n; i <= N; i++) {
    result *= i;
  }
  return result; // BigInt
}

// Приклади
console.log(factorial(0).toString());  // "1"
console.log(factorial(5).toString());  // "120"
console.log(factorial(25).toString()); // "15511210043330985984000000"

Python:

def factorial(n: int) -> int:
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be >= 0")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Приклади виклику
print(factorial(0))   # 1
print(factorial(5))   # 120
print(factorial(25))  # 15511210043330985984000000

# Примітка: у стандартній бібліотеці є готова функція math.factorial(n).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.