nPr — перестановки: формула и примеры на Python, C++, JavaScript, C и Java

Что такое перестановка (одно предложение)

Перестановка — это упорядоченное размещение элементов, где порядок важен.

Формула

Используется стандартная формула перестановок:

nPr = n! / (n - r)!

Где:

• n — общее число элементов
• r — число выбираемых элементов (порядок важен)
• ! — факториал (например, 5! = 120)

Быстрые примеры

• n=10, r=5 → nPr = 10! / 5! = 30240
• n=3, r=2 → nPr = 3! / 1! = 6
• n=8, r=0 → nPr = 8! / 8! = 1

Частые ошибки и проверки (когда не получится)

• r > n — перестановки не определены; следует вернуть ошибку или 0.
• r < 0 или n < 0 — недопустимые входные данные.
• Переполнение типов: факториалы растут очень быстро (20! уже ≈ 2.43e18), используйте BigInt/long long/BigInteger или вычисляйте через последовательное умножение.

Важно: для практических задач лучше не вычислять n! и (n-r)! отдельно — это дорого и рисковано. Вычисляйте nPr, перемножая n × (n-1) × … × (n-r+1).

Эффективный подход (метод)

Мини-методология для безопасного вычисления nPr:

1. Проверить валидность: 0 ≤ r ≤ n и n ≥ 0.
2. Если r == 0, вернуть 1.
3. Вычислять произведение последовательно от n до n-r+1, контролируя тип и переполнение.
4. При необходимости использовать целые расширенной точности (BigInt/BigInteger).

Ментальная модель

Факториал — сколько упорядоченных способов расположить все элементы; перестановки nPr — это та же идея, но мы останавливаемся после r мест.

C++ — рекурсивный и итеративный (рекомендация: итеративный)

Ниже первый вариант (рекурсивный), как в исходнике, и затем итеративный безопасный вариант.

// C++ программа: рекурсивный факториал (работает для небольших n)
#include 
using namespace std;

long long factorial(int num) {
    if (num <= 1) return 1;
    return num * factorial(num - 1);
}

long long calculate_nPr_recursive(int n, int r) {
    return factorial(n) / factorial(n - r);
}

// Итерируемый безопасный вариант для nPr — не вычисляет полные факториалы
long long calculate_nPr_iterative(int n, int r) {
    if (r < 0 || r > n) return 0; // либо бросать исключение
    long long result = 1;
    for (int i = 0; i < r; ++i) {
        result *= (n - i);
    }
    return result;
}

int main() {
    cout << "n: 10, r: 5\nValue of nPr: " << calculate_nPr_iterative(10, 5) << endl;
    cout << "n: 3, r: 2\nValue of nPr: " << calculate_nPr_iterative(3, 2) << endl;
    cout << "n: 8, r: 0\nValue of nPr: " << calculate_nPr_iterative(8, 0) << endl;
    return 0;
}

Вывод примера:

n: 10, r: 5
Value of nPr: 30240
n: 3, r: 2
Value of nPr: 6
n: 8, r: 0
Value of nPr: 1

Python — рекурсивный и встроенный метод

Если вы пользуетесь Python 3.8+, есть функция math.perm, которая делает всё корректно и быстро.

# Рекурсивный факториал (подойдёт для учебных примеров)
def factorial(num):
    if num <= 1:
        return 1
    return num * factorial(num - 1)

# Рекомендуемый вариант: последовательное умножение
def calculate_nPr(n, r):
    if r < 0 or r > n:
        raise ValueError('r must be between 0 and n')
    result = 1
    for i in range(r):
        result *= (n - i)
    return result

# Альтернатива (Python 3.8+):
# import math
# math.perm(n, r)

print('n:', 10, ', r:', 5)
print('Value of nPr:', calculate_nPr(10, 5))

JavaScript — рекурсивный и итеративный

В браузере используйте BigInt, если значения большие.

// Итеративный вариант с проверкой
function calculate_nPr(n, r) {
  if (r < 0 || r > n) return 0;
  let result = 1n; // используем BigInt для безопасности
  for (let i = 0; i < r; i++) {
    result *= BigInt(n - i);
  }
  return result;
}

console.log('n: 10, r: 5');
console.log('Value of nPr:', calculate_nPr(10, 5).toString());

C — итеративный вариант

Рекурсивный факториал в C подвержен переполнению и стековому ограничению; ниже итеративный подход.

#include 
#include 

uint64_t calculate_nPr(int n, int r) {
    if (r < 0 || r > n) return 0;
    uint64_t result = 1;
    for (int i = 0; i < r; ++i) result *= (uint64_t)(n - i);
    return result;
}

int main() {
    printf("n: 10, r: 5\nValue of nPr: %llu\n", calculate_nPr(10, 5));
    return 0;
}

Java — итеративный и BigInteger

Для больших n используйте java.math.BigInteger.

import java.math.BigInteger;

public class Main {
    static BigInteger calculate_nPr(int n, int r) {
        if (r < 0 || r > n) return BigInteger.ZERO;
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < r; i++) {
            result = result.multiply(BigInteger.valueOf(n - i));
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("n: 10, r: 5");
        System.out.println("Value of nPr: " + calculate_nPr(10, 5));
    }
}

Факт-бокс: ключевые числа

• 0 ≤ r ≤ n — допустимый диапазон.
• Факториалы растут сверхэкспоненциально: 10! = 3 628 800; 20! ≈ 2.43×10^18.
• Для практики используйте итеративный подсчёт nPr, чтобы уменьшить временные и пространственные затраты.

Когда не применять этот метод

• Когда важен только набор элементов без порядка — тогда используется сочетание (nCr).
• Для очень больших n,r с ограничениями по времени/памяти нужно использовать комбинаторные приближения или логарифмические вычисления.

Контроль качества — чеклист для разработчика

• Проверить входы: n и r неотрицательны.
• Обрабатывать r > n (ошибка или 0).
• Выбрать тип данных (int, long long, BigInteger, BigInt).
• Тестировать граничные случаи: r=0, r=n, n=0.
• Добавить тесты на переполнение.

Пример набора тестов (критерии приёмки)

• n=10, r=5 → 30240
• n=3, r=2 → 6
• n=8, r=0 → 1
• r > n → вернуть 0 или бросить исключение
• крупные значения с BigInt/BigInteger должны возвращать корректный результат

Небольшое дерево решения

flowchart TD
  A[Есть n и r?] --> B{r < 0 или r > n}
  B -- Да --> C[Ошибка или вернуть 0]
  B -- Нет --> D{r == 0}
  D -- Да --> E[Вернуть 1]
  D -- Нет --> F[Вычислить произведение n*'n-1'*...*'n-r+1']
  F --> G[Проверить тип: нужен BigInt?]
  G -- Да --> H[Использовать BigInteger/BigInt]
  G -- Нет --> I[Вернуть результат как целое]

Итог

Перестановки nPr вычисляются по формуле n!/(n-r)!, но для надёжности и эффективности применяйте итеративное умножение от n до n-r+1 и контролируйте типы данных. В продуктивном коде учитывайте проверки входных данных и тесты на переполнение.

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