Мешок

Определения и обозначения

Мешок — коллекция элементов, в которой порядок не важен, но одинаковые элементы могут встречаться несколько раз. Например, {красный, синий, красный} и {синий, красный, красный} — один мешок. Такое описание удобно, когда нужно учитывать состав и повторы, но не очередность перечисления.

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

Кратность элемента — число его вхождений в мешок. В {а, б, а} кратность а равна двум, а кратность б — одному. Простое наличие сообщает только, что элемент встречается хотя бы раз, а кратность показывает точное число повторений.

Пустой мешок — мешок, в котором нет элементов. Его можно представить как {}. Это обозначение помогает отличить отсутствие содержимого от мешка, где есть хотя бы одно значение.

Как это устроено

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

Задают мешок перечислением его элементов внутри фигурных скобок, например {2, 4, 2, 5}. Перечень показывает значения и их повторы, но не задаёт места каждого элемента. Поэтому перестановка записи, например {5, 2, 2, 4}, не меняет мешок: количество каждого значения осталось прежним. Чтобы проверить это, можно посчитать кратность каждого элемента в обеих записях.

Кратность меняется при добавлении или удалении вхождений. Если к мешку {2, 4, 2, 5} добавить ещё одну двойку, получится {2, 4, 2, 5, 2}, а кратность числа 2 возрастёт с двух до трёх. Причина проста: добавление создаёт ещё одно вхождение, не заменяя уже имеющиеся. Остальные элементы при этом остаются без изменений.

Удаление тоже относится к вхождениям, поэтому важно уточнить, сколько элементов требуется убрать. Удаление одного вхождения числа 2 из {2, 4, 2} оставит, например, {2, 4}; кратность двойки станет равна единице. Удаление всех двоек дало бы другой результат — {4}. Так различают изменение кратности на единицу и полное исчезновение значения.

Два мешка равны, если в них совпадают все значения и кратности этих значений. Например, {1, 1, 3} и {3, 1, 1} равны, потому что в каждом две единицы и одна тройка. А мешки {1, 3} и {1, 1, 3} не равны: единица есть в обоих, но её кратности различаются. Для сравнения удобно составить список уникальных значений и проверить каждое по очереди.

Основные свойства и действия с мешком

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

Разбор задач

Задача 1. Дан мешок {а, б, а}. Запишите его после перестановки элементов и укажите, изменился ли мешок.

1. Сначала посчитаем вхождения: а встречается два раза, б — один раз.
2. Переставим запись, например поставим б первым: получим {б, а, а}.
3. Сравним кратности: они не изменились, потому что ни один элемент не добавлен и не убран.

Ответ: после перестановки можно записать {б, а, а}; мешок не изменился. Мы проверяли состав по кратностям, а не расположение записей.

Задача 2. В мешке {2, 4, 2, 5} увеличьте кратность числа 2 на единицу, затем удалите одно вхождение числа 4.

1. В исходном мешке две двойки. Чтобы увеличить их кратность на единицу, добавим ещё одно вхождение числа 2: {2, 4, 2, 5, 2}.
2. Теперь найдём число 4. Оно встречается один раз, поэтому удаление одного вхождения уберёт его полностью.
3. Оставим все остальные значения без изменений и запишем результат: {2, 2, 5, 2}.

Ответ: получился мешок {2, 2, 5, 2}. В нём кратность числа 2 равна трём, а числа 4 нет.

Задача 3. Даны мешки A = {1, 1, 2, 3, 3} и B = {3, 1, 3, 2, 1}. Определите, равны ли они; затем выясните, как изменится A, если удалить все вхождения числа 3.

1. Проверим уникальные значения: 1, 2 и 3. В A и B у числа 1 кратность два, у числа 2 — один, у числа 3 — два.
2. Все кратности совпали, значит, мешки равны. Разный порядок записи этому не мешает.
3. В A удаляем оба вхождения числа 3, поскольку условие говорит «все». Числа 1 и 2 оставляем на месте в мешке.

Ответ: A и B равны. После удаления всех троек из A останется {1, 1, 2}; при удалении только одного вхождения в мешке сохранилась бы ещё одна тройка.

Типичные ошибки

Ошибка — считать мешок и множество одним и тем же. Так думают, потому что оба объекта описывают коллекции, но у множества повторные записи не меняют состав, а у мешка они увеличивают кратность. Проверьте себя вопросом: изменится ли содержимое, если добавить ещё одно такое же значение? Для мешка изменится.

Ошибка — объявлять мешки разными из-за разного порядка перечисления. Порядок записи легко принять за порядок элементов, как в списке, но для мешка он не задаёт отдельного свойства. Составьте подсчёт вхождений и сравните кратности; если они совпадают, мешки равны.

Ошибка — при удалении одного элемента убирать все одинаковые вхождения. Такое происходит, если не уточнить смысл слова «элемент», однако удаление одного вхождения уменьшает кратность только на единицу. Перед действием пересчитайте повторы и после удаления проверьте, не должны ли некоторые из них остаться.

Ошибка — сравнивать мешки только по наличию значений. Можно заметить, что в обоих есть число 1, и пропустить разницу между одной и двумя единицами. Проверка должна учитывать каждое значение и его кратность, а не только перечень разных элементов. Если хотя бы одна кратность не совпала, мешки не равны.

Связь с другими темами

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

Что запомнить

• В мешке порядок элементов не важен.
• Одинаковые элементы могут встречаться несколько раз.
• Кратность показывает число вхождений элемента.
• Добавление элемента увеличивает его кратность на единицу.
• При удалении одного вхождения остальные одинаковые элементы могут остаться.
• Равенство мешков проверяют по кратностям всех элементов.