EssayAI
Блог
Блог
Естественные науки

Мультимножество: кратности, операции и примеры

8 ноября 2026Время чтения: 8 минут
#мультимножество#кратность элемента#структуры данных#операции над множествами#комбинаторика
Мультимножество: кратности, операции и примеры

Мультимножество - это набор, в котором учитывают, сколько раз встречается каждый элемент, но не учитывают порядок элементов. Например, корзина из трёх яблок и одной груши отличается от корзины с одним яблоком и одной грушей. Обычное множество видит в обеих корзинах только два вида фруктов, а мультимножество сохраняет ещё и количество каждого вида.

Это представление полезно для частот слов, остатков товаров, коллекций с повторами и комбинаторных задач. В калькуляторе задайте количества трёх видов фруктов для двух корзин и сравните результаты операций: особенно полезно проследить, почему объединение и сумма могут давать разные ответы.

Кратность и порядок

Запишем корзину как A={a,a,a,b}A=\{a,a,a,b\}, где aa означает яблоко, а bb - грушу. Кратность mA(x)m_A(x) показывает число вхождений элемента xx: здесь mA(a)=3m_A(a)=3, mA(b)=1m_A(b)=1, а кратность отсутствующей сливы mA(c)=0m_A(c)=0. Фигурные скобки с повторами в этой статье обозначают именно мультимножество; иногда для ясности используют двойные скобки.

Перестановка записи не меняет набора: {a,a,b}={b,a,a}\{a,a,b\}=\{b,a,a\}. Но {a,a,b}≠{a,b,b}\{a,a,b\}\ne\{a,b,b\}: кратности яблока и груши различаются. Это отличие и от списка, в котором позиции важны, и от обычного множества, где повторная запись элемента ничего не добавляет. Подробнее об обычных операциях над множествами можно прочитать отдельно.

Яблоки добавляются по одному и затем убираются: кратность яблока и общее число элементов меняются вместе, а число видов остаётся прежним.

На ролике одна груша остаётся на месте. Когда число яблок растёт с одного до трёх, общее количество фруктов растёт с двух до четырёх. Сами яблоки одного вида считаются неразличимыми: их положение на рисунке не является частью данных мультимножества.

Мощность и носитель

Для конечного мультимножества сумма всех кратностей даёт его мощность, то есть число элементов с учётом повторений:

∣A∣=∑xmA(x).|A|=\sum_x m_A(x).

У нашей корзины ∣A∣=3+1=4|A|=3+1=4. А носитель - обычное множество элементов с положительной кратностью: supp⁡(A)={a,b}\operatorname{supp}(A)=\{a,b\}. Его мощность равна двум. Сначала уточняйте, спрашивают ли количество всех объектов или количество различных видов: это разные величины.

Мультимножество можно задать таблицей пар «элемент - кратность»: (a,3)(a,3), (b,1)(b,1). Отсутствующие элементы имеют нулевую кратность и обычно в таблицу не попадают. Такая форма особенно удобна, если повторений много: миллион одинаковых ключей можно описать одним ключом и счётчиком, хотя конкретная реализация может хранить данные иначе.

Два мультимножества равны тогда и только тогда, когда кратности каждого возможного элемента равны. Аналогично AA является подмультимножеством BB, если для каждого xx выполнено mA(x)≤mB(x)m_A(x)\le m_B(x). Например, {a,a}\{a,a\} входит в {a,a,b}\{a,a,b\}, но не входит в {a,b}\{a,b\}: одного яблока недостаточно.

Пересечение и объединение

Возьмём два мультимножества A={a,a,a,b}A=\{a,a,a,b\} и B={a,b,b,c}B=\{a,b,b,c\}. В порядке «яблоко, груша, слива» их кратности равны (3,1,0)(3,1,0) и (1,2,1)(1,2,1). Для каждого вида отдельно применим два правила:

mA∩B(x)=min⁡(mA(x),mB(x)),mA∪B(x)=max⁡(mA(x),mB(x)).m_{A\cap B}(x)=\min(m_A(x),m_B(x)),\qquad m_{A\cup B}(x)=\max(m_A(x),m_B(x)).

В пересечение попадает столько копий, сколько одновременно можно взять из каждой корзины. Для яблок минимум равен одному, для груш - одному, а для слив - нулю. Значит, A∩B={a,b}A\cap B=\{a,b\} с кратностями (1,1,0)(1,1,0) и мощностью 22.

Для объединения берём максимум, поэтому получаем (3,2,1)(3,2,1), или {a,a,a,b,b,c}\{a,a,a,b,b,c\}. Его мощность равна 66. Это определение продолжает привычные операции над множествами: если кратности ограничены нулём и единицей, минимум работает как логическое «и», а максимум - как «или».

Таблица кратностей двух мультимножеств и результатов пересечения, объединения, суммы и разности
Таблица кратностей двух мультимножеств и результатов пересечения, объединения, суммы и разности

В каждой колонке схемы сравнивается один вид, а не общее число фруктов. Например, одна груша в пересечении получается как минимум из одного и двух; две груши в объединении - как максимум. В разных источниках обозначения операций могут отличаться, поэтому важнее прочитать определение через кратности, чем угадывать его по знаку.

Сумма и разность: считаем копии

Если корзины физически ссыпать вместе, нужно сложить кратности. Для суммы A⊎BA\uplus B правило такое:

mA⊎B(x)=mA(x)+mB(x).m_{A\uplus B}(x)=m_A(x)+m_B(x).

Получаем (4,3,1)(4,3,1) и восемь фруктов. Это не то же самое, что объединение по максимуму (3,2,1)(3,2,1) с шестью фруктами. Например, три яблока из первой корзины и одно из второй вместе дают четыре яблока, а максимум кратностей равен трём. Название «объединение» иногда используют и для сложения; в задаче необходимо выяснить, какое правило задано.

Разность A∖BA\setminus B вычитает кратности, но не опускает результат ниже нуля:

mA∖B(x)=max⁡(mA(x)−mB(x),0).m_{A\setminus B}(x)=\max(m_A(x)-m_B(x),0).

В примере остаются два яблока: (2,0,0)(2,0,0). Одной груши недостаточно, чтобы вычесть две, поэтому результат для груш равен нулю, а не минус одному. Разность зависит от порядка: B∖AB\setminus A имеет кратности (0,1,1)(0,1,1). Для контроля удобно проверить мощность суммы: ∣A⊎B∣=∣A∣+∣B∣=8|A\uplus B|=|A|+|B|=8. Кроме того, покомпонентное равенство минимума плюс максимума сумме даёт ∣A∩B∣+∣A∪B∣=8|A\cap B|+|A\cup B|=8.

Применение в программах

Частотный словарь хранит для каждого ключа число его вхождений. Так можно сравнить состав двух текстов по словам, проверить наличие нужного количества деталей на складе или определить, можно ли из набора букв собрать слово. В последнем случае кратность каждой требуемой буквы должна не превышать доступную; простой проверки принадлежности буквы недостаточно.

В Python класс collections.Counter хранит счётчики в словаре. Для положительных целых кратностей операторы & и | дают соответственно минимум и максимум, + складывает счётчики, а - оставляет только положительные разности:

from collections import Counter

a = Counter({'a': 3, 'b': 1})
b = Counter({'a': 1, 'b': 2, 'c': 1})
print(a & b)  # a: 1, b: 1
print(a | b)  # a: 3, b: 2, c: 1
print(a + b)  # a: 4, b: 3, c: 1
print(a - b)  # a: 2

Сам Counter допускает нулевые и отрицательные значения: это полезно для промежуточных вычислений, но не обычная модель конечного мультимножества с неотрицательными целыми кратностями. При арифметических операциях результаты с неположительными счётчиками исключаются. В Java аналогичное понятие описывает интерфейс Guava Multiset: он различает число всех вхождений и множество различных элементов.

Подмультимножества и комбинаторика

Пусть A={a,a,a,b,b}A=\{a,a,a,b,b\}. В подмультимножество можно взять ноль, одно, два или три яблока и независимо ноль, одну или две груши. По правилу произведения получаем 4⋅3=124\cdot3=12 подмультимножеств, включая пустое и исходное. Мы выбираем кратность каждого вида, а не отдельные физические копии: выбор первого яблока и выбор второго дают один результат.

В общем случае для положительных кратностей n1,…,nkn_1,\ldots,n_k ответ равен ∏i=1k(ni+1)\prod_{i=1}^{k}(n_i+1). Сравните его с числом подмножеств обычного множества: там все ni=1n_i=1, поэтому получается 2k2^k. Когда же требуется расположить все элементы в ряд, порядок уже важен и применяется другая задача - перестановки с повторениями. Не смешивайте число возможных составов с числом их расположений.

Как решить задачу по шагам

Предположим, что для ремонта нужны два винта одного размера и одна шайба. На складе лежат три таких винта и одна шайба. Сравнивать здесь следует не только названия деталей: одна и та же деталь может понадобиться несколько раз. Составьте две таблицы частот, причём в обеих используйте одинаковые обозначения видов. Затем для каждой строки сравните требуемое количество с доступным. Если ни одна потребность не превышает запас, заказ можно собрать целиком.

В этом примере условие выполняется: два винта не превышают три, а одна шайба не превышает одну. После выдачи заказа в запасе останется один винт. Если же потребовать две шайбы, проверка не пройдёт, хотя слово «шайба» присутствует в списке запасов. Пересечение покажет, сколько деталей каждого вида можно покрыть имеющимся запасом; нехватку можно получить, вычитая запас из потребности с отсечением на нуле.

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

Для ручной проверки выпишите также виды, встречающиеся только в одном наборе. У второго набора для них кратность равна нулю. В пересечение такой вид не попадёт, в объединении сохранится положительная кратность, а в направленной разности результат зависит от того, из какой стороны выполняется вычитание. Эта проверка помогает не пропустить элементы при переходе от таблицы к ответу.

Частые ошибки

  • Терять повторы. Носители {a,b}\{a,b\} совпадают у {a,a,b}\{a,a,b\} и {a,b,b}\{a,b,b\}, но сами мультимножества различны.
  • Складывать вместо максимума. В принятом здесь определении объединения кратность яблока равна max⁡(3,1)=3\max(3,1)=3, а в сумме - 44.
  • Путать число видов с мощностью. В A={a,a,a,b}A=\{a,a,a,b\} два вида, но четыре элемента с учётом повторов.
  • Вычитать отрицательные кратности. Обычная разность мультимножеств обрезает отрицательный результат до нуля; отрицательный счётчик в программе требует отдельной интерпретации.
  • Учитывать порядок при сравнении. Перестановка записанных элементов не меняет кратностей и потому не меняет мультимножество.

Частые вопросы

Может ли мультимножество быть пустым?

Да. У пустого мультимножества кратность любого элемента равна нулю, носитель пуст, а мощность равна нулю.

Является ли обычное множество мультимножеством?

Да, его можно представить мультимножеством, в котором кратность каждого элемента равна нулю или единице. Обычные объединение и пересечение тогда совпадают с правилами максимума и минимума.

Чем мультимножество отличается от массива?

Массив хранит элементы по индексам, и их порядок имеет значение. Мультимножество учитывает только значение и число его появлений. Из массива можно получить мультимножество подсчётом частот, но восстановить исходный порядок по одним частотам нельзя.

Коротко

Мультимножество хранит кратности без учёта порядка. Его мощность - сумма кратностей, пересечение берёт минимум, объединение - максимум, сумма складывает количества, а разность вычитает их с отсечением на нуле. Проверка каждого вида по отдельности делает операции и связанные с ними задачи прозрачными.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Перестановки с повторениями: формула и примеры

Перестановки с повторениями: формула и примеры

Перестановки с повторениями: как работает формула n! делить на произведение факториалов повторов, почему она именно такая, разбор слова МАТЕМАТИКА, шаров и маршрутов, частые ошибки.

11 июня 20267 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

8 ноября 20269 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

8 ноября 20268 минут
Диаграммы Юнга: разбиения, таблицы и формула крюков

Диаграммы Юнга: разбиения, таблицы и формула крюков

Диаграммы Юнга на примерах: как построить форму разбиения, получить сопряжённую диаграмму и посчитать стандартные таблицы с помощью формулы крюков на подробном примере.

8 ноября 20268 минут
Комбинаторика: размещения и формулы подсчёта

Комбинаторика: размещения и формулы подсчёта

Размещения в комбинаторике: как учитывать порядок и повторения, вывести формулу, решить задачи с ограничениями и проверить ответ на конкретных примерах с разбором.

8 ноября 20268 минут
Метод шаров и перегородок: формулы и примеры

Метод шаров и перегородок: формулы и примеры

Метод шаров и перегородок помогает считать распределения одинаковых предметов и решения целочисленных уравнений. Разбираем формулы, ограничения и примеры.

8 ноября 20268 минут