Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Размещение без повторений - это упорядоченное расположение $k$ элементов, выбранных из $n$ различных элементов, в $k$ позициях. Каждый выбранный элемент используется только один раз, и порядок элементов имеет значение.

---

Формула

$\Huge{A(n, k) = \frac{n!}{(n-k)!}}$

Где:

• $A(n,k)$ - количество размещений без повторений из $n$ элементов по $k$ элементов.
• $n!$ - факториал числа $n$.
• $(n−k)!$ - факториал числа $n−k$, равен произведению всех положительных целых чисел от $1$ до $n−k$.

Принцип работы

Пусть у нас есть набор {A, B, C, D}, и мы хотим выбрать и упорядочить 2 элемента из этого набора.

Определение переменных:

• $n$ — общее количество элементов, из которых мы выбираем. Здесь: $n=4$, так как у нас есть 4 элемента: A, B, C, D.
• $k$ — количество элементов, которые мы выбираем и упорядочиваем из общего числа $n$. В этом примере: $k=2$, так как нам нужно выбрать и упорядочить два элемента из четырёx.

Разберем все по шагам:

• Шаг 1: Подсчёт количества размещений без повторений Число размещений из $n$ по $k$ без повторений рассчитывается по формуле: ${A(n, k) = \frac{n!}{(n-k)!}}$

• Шаг 2: Подстановка значений Подставим значения $n=4$ и $k=2$ в формулу: $A(4, 2) = \frac{4!}{(4-2)!} = 12$

• Шаг 3: Проверка результата (перечисление размещений) Перечислим все возможные варианты выбора и упорядочивания 2 элементов из 4: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

Всего 12 уникальных вариантов, что соответствует расчётам.

Вычислительная сложность

Вычислительная сложность $O(k)$: Поскольку для $A(n,k)$ нужно перемножить только $k$ членов из $n!$, сложность вычисления также пропорциональна $k$.

Пространственная сложность

Пространственная сложность - $O(1)$, потому что память остается постоянной, так как все вычисления идут с сохранением промежуточного результата.

---

Применение

Размещения без повторений имеют широкий спектр применений в различных областях:

1. Комбинаторика: Размещения без повторений широко используются в комбинаторике для решения различных задач, таких как перестановки, сочетания и размещения. Например, они могут быть использованы для вычисления количества способов разместить n элементов в определенном порядке.

2. Cтатистика: В статистике размещения без повторений могут быть использованы для моделирования случайных выборок из заданного множества. Это может быть полезно при проведении экспериментов или опросов.

3. Информатика: В информатике размещения без повторений применяются в алгоритмах, связанных с упорядоченными данными. Например, при генерации всех возможных перестановок элементов в массиве.

---

Готовые функции в Python

В Python, библиотека itertools предоставляет функции для работы Размещениями без повторений, например:

• permutations(iterable, r) - функция, которая генерирует все возможные перестановки длины r из итерируемого объекта iterable. Она возвращает объект-генератор, который может быть использован для перебора всех перестановок.

---

Готовые функции в C++

В C++, библиотека <algorithm> предоставляет функции для работы с перестановками без повторений. Некоторые из них:

• next_permutation() - функция переставляет элементы в диапазоне так, чтобы они образовывали следующую лексикографическую перестановку. Если такой перестановки больше нет, функция вернет false.

---

Псевдокод

Функция arrangements_without_repetition(elements: список, size: целое) -> целое:
    Если size > длина(elements), то
        Вернуть 0

    numerator <- Факториал(длина(elements))
    denominator <- Факториал(длина(elements) - size)

    result <- numerator / denominator

    Вернуть result

---

Реализация на Python

Аннотация:
arrangements_without_repetition - функция для вычисления количества размещений без повторений для заданной последовательности элементов
elements - последовательность элементов
size - размер размещения
numerator - факториал длины последовательности элементов
denominator - факториал разности между длиной последовательности элементов и размером размещения
result - результат вычисления количества размещений без повторений

import math

def arrangements_without_repetition(elements, size):
    if size > len(elements):
        return 0

    numerator = math.factorial(len(elements))
    denominator = math.factorial(len(elements) - size)

    result = numerator // denominator

    return result

---

Олимпиадная реализация на С++

Аннотация:
elements - последовательность элементов, представленных в виде вектора символов
size - размер размещения
num - числитель, представляющий собой факториал длины последовательности элементов
denom - знаменатель, представляющий собой факториал разности между длиной последовательности элементов и размером размещения
res - результат вычисления количества размещений без повторений

#include <iostream>
#include <vector>

using namespace std;

long long arrangements_without_repetition(vector<char>& elements, int size){

    if (size > elements.size()) {
        return 0;
    }

    long long num = 1;
    for (int i = 1; i <= elements.size(); i++) {
        num *= i;
    }

    long long denom = 1;
    for (int i = 1; i <= elements.size() - size; i++) {
        denom *= i;
    }

    long long res = num / denom;

    return res;
}

---

Продуктовая реализация на С++

Аннотация:
factorial - функция нахождения факториала числа
n - число, факториал которого нужно найти
result - результат выполнения факториала
permutations_without_repetition - функция перестановок без повторений
size - размер последовательности

#include <iostream>
#include <vector>

using namespace std;

long long factorial(int n) {
    long long res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

long long arrangements_without_repetition(vector<char>& elements, int size) {
    if (size > elements.size()) {
        return 0;
    }

    long long numerator = factorial(elements.size());
    long long denominator = factorial(elements.size() - size);
    long long result = numerator / denominator;

    return result;
}