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

Определение

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

---

Формула

$\Huge{{{P}_{n_1,n_2,\ldots,n_k}} = \frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}}$

Где:

• $n$ - количество элементов
• $n!$ - факториал числа $n$

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

Допустим, у нас есть набор букв {A, A, B, B}. Мы хотим узнать, сколько уникальных перестановок можно составить из этих букв.

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

• $n$ — общее количество элементов в наборе. Здесь $n=4$.
• $n_1$​ и $n_2$​ — количество повторяющихся элементов для каждой уникальной буквы: Буква "A" встречается 2 раза: $n_1=2$, и буква "B" встречается 2 раза: $n_2=2$

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

• Шаг 1: Вычисление перестановок без учета повторений Сначала считаем, сколько всего перестановок можно было бы сделать, если бы все элементы были уникальны. Формула: $x=n!$ В нашем примере: $x=4!=24$ Это означает, что если бы буквы не повторялись, можно было бы создать 24 различных комбинации.

• Шаг 2: Учет повторений Теперь учитываем, что буквы "A" и "B" повторяются, поэтому перестановки с одинаковыми буквами не будут уникальными. Считаем перестановки для повторяющихся элементов: Для двух букв "A": $n_1!=2!=2$ и для двух букв "B": $n_2!=2!=2$ Перемножаем результаты: $k=n_1!*n_2!=2*2=4$ Здесь $k=4$ — это количество повторяющихся перестановок, которые мы должны исключить.

• Шаг 3: Расчет итогового количества уникальных перестановок Теперь найдем итоговое количество уникальных перестановок, разделив общее число перестановок на число повторяющихся комбинаций. Формула: $P=x/k$ Подставляем значения: $P=24/4=6$

• Шаг 4: Проверка результата (перечисление перестановок) Для наглядности перечислим все возможные уникальные перестановки "AABB": AABB, ABAB, ABBA, BAAB, BABA, BBAA.

Получается ровно 6 уникальных перестановок, что подтверждает правильность расчетов.

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

Вычислительная сложность $O(n)$: Вычисление числителя требует $O(n)$ операций для факториала $n$, знаменатель добавляет $\sum_O(n_i)$ , что также пропорционально $n$.

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

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

---

Применение

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

1. Комбинаторика: Используются для анализа комбинаторных задач, где необходимо учесть возможность повторения элементов.

2. Статистика: Могут использоваться при анализе данных, например, в задачах, связанных с перебором возможных вариантов.

3. Криптография: Перестановки с повторениями могут быть использованы в различных алгоритмах шифрования.

---

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

В Python, библиотека itertools предоставляет более гибкие средства для работы с перестановками с повторениями. Некоторые из них:

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

---

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

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

Например, функция next_permutation() может быть использована для генерации перестановок, но она не учитывает повторения элементов.

Псевдокод

Функция ВычислитьПерестановкиСПовторениями(элементы):
    elementCounts <- СоздатьПустойСловарь()

    Для каждого элемента в элементы:
        Если элемент в elementCounts:
            elementCounts[элемент] <- elementCounts[элемент] + 1
        Иначе:
            elementCounts[элемент] <- 1

    n <- ПолучитьДлину(элементы)
    numerator <- ВычислитьФакториал(n)

    denominator <- 1
    Для каждого count в Значения(elementCounts):
        denominator <- denominator * ВычислитьФакториал(count)

    результат <- numerator / denominator

    Вернуть результат

---

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

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

import math

def permutations_with_repetition(elements):
    element_counts = {}

    for element in elements:
        if element in element_counts:
            element_counts[element] += 1
        else:
            element_counts[element] = 1

    n = len(elements)
    numerator = math.factorial(n)

    denominator = 1
    for count in element_counts.values():
        denominator *= math.factorial(count)

    result = numerator // denominator

    return result

---

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

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

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

long long perms_with_rep(vector<int>& elements){

    unordered_map<int, int> elem_counts;

    for (int element : permutation) {
        if (elem_counts.find(element) != elem_counts.end()) {
            elem_counts[element]++;
        } else {
            elem_counts[element] = 1;
        }
    }

    int n = permutation.size();

    long long num = 1;
    for (int i = 1; i <= n; i++) {
        num *= i;
    }

    long long denom = 1;
    for (const auto& kv : element_counts) {
        int count = kv.second;
        for (int i = 1; i <= count; i++) {
            denom *= i;
        }
    }

    long long res = num / denom;

    return res;
}

---

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

Аннотация
factorial - функция вычисления факториала числа n
n - число, факториал которого нужно вычислить
res - результат вычисления факториала
permutations_with_repetition - функция вычисления количества перестановок с повторениями для заданного списка элементов
elements - ссылка на вектор элементов, для которого вычисляется количество перестановок с повторениями
element_counts - словарь для подсчета количества каждого уникального элемента в перестановке
n - общее количество элементов в перестановке
numerator - числитель, представляющий собой факториал общего количества элементов
denominator - знаменатель, представляющий собой произведение факториалов количества каждого уникального элемента
result - результат вычисления, представляющий собой количество перестановок с повторениями

#include <iostream>
#include <vector>
#include <unordered_map>

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 permutations_with_repetition(vector<int>& elements) {
    unordered_map<int, int> element_counts;

    for (int element : elements) {
        if (element_counts.find(element) != element_counts.end()) {
            element_counts[element]++;
        } else {
            element_counts[element] = 1;
        }
    }

    int n = elements.size();
    long long numerator = factorial(n);

    long long denominator = 1;
    for (const auto& kv : element_counts) {
        int count = kv.second;
        denominator *= factorial(count);
    }

    long long result = numerator / denominator;
    return result;
}