Мешок

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

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

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

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

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

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

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

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

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

Размер находят подсчётом всех записанных вхождений или сложением кратностей различных элементов. Например, если одно значение встречается дважды, а другое трижды, размер равен 2 + 3 = 5. Нельзя считать только различные значения: такой подсчёт показывает число видов элементов, а не размер мешка. Повторы увеличивают размер, потому что каждый из них является отдельным элементом коллекции.

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

Свойства мешка и способы их определять

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

Разбор задач

Задача. Даны мешки {красный, синий, красный} и {синий, красный, красный}. Определите, равны ли они. Сравнивать записи по порядку не нужно, потому что в мешке расположение элементов не учитывается. Проверим, одинаковы ли количества каждого цвета.

1. Подсчитаем красные элементы: в первом мешке их два, и во втором тоже два. Значит, кратности красного совпадают.
2. Подсчитаем синие элементы: в каждом мешке он встречается один раз. Других цветов в записях нет, поэтому сравнение завершено.
3. Все кратности совпали, хотя синий и красный перечислены в разном порядке. Следовательно, мешки равны.

Ответ: мешки равны. Проверка по кратностям надёжнее сравнения записей: она учитывает именно те свойства, которые определяют мешок. Достаточно проверить каждое встречающееся значение, а не переставлять элементы для совпадения строк.

Задача. В мешке {2, 5, 2, 7, 5, 2} найдите кратность числа 2 и размер мешка. Для кратности считаем только вхождения числа 2. Для размера учитываем все элементы, в том числе повторяющиеся числа.

1. Найдём все двойки в записи: число 2 стоит на первом, третьем и шестом местах. Значит, оно встречается три раза.
2. Пересчитаем все элементы: в записи шесть значений. Можно проверить и сложением кратностей: у 2 кратность 3, у 5 — 2, у 7 — 1, всего 3 + 2 + 1 = 6.
3. Кратность числа 2 равна 3, а размер мешка равен 6. Различных значений здесь три, но это не размер, потому что некоторые из них повторяются.

Ответ: кратность числа 2 — 3, размер мешка — 6. Раздельный подсчёт помогает не перепутать количество выбранного значения с общим числом элементов. Сложение кратностей служит дополнительной проверкой размера.

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

1. Изначально а встречается два раза, б — один раз, в — один раз; размер равен четырём. Удаление одного а уменьшает его кратность с двух до одного, поэтому остаются {а, б, в}.
2. Теперь добавим б: его кратность увеличивается с одного до двух. Новый мешок можно записать как {а, б, в, б}; порядок записи на результат не влияет.
3. Пересчитаем элементы нового мешка: один а, два б и один в. Получаем размер 1 + 2 + 1 = 4, что также подтверждается изменениями: сначала размер уменьшился на единицу, затем увеличился на единицу.

Ответ: новый мешок {а, б, в, б}, его размер равен 4. Удаление одного вхождения не стерло вторую букву а, а добавление б создало ещё одно её вхождение. Размер вернулся к исходному, поскольку два действия изменили его в противоположных направлениях на одинаковую величину.

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

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

• Считать одинаковые элементы одним элементом — значит терять сведения о повторениях. Так делают, когда замечают только различные значения, не пересчитывая каждое вхождение. Проверьте запись по элементам: каждое повторное значение должно быть учтено и в кратности, и в размере.

• Определять равенство мешков только по набору различных значений недостаточно: одинаковые значения могут встречаться с разной частотой. Такая ошибка возникает, если сравнить лишь список видов элементов. Для проверки найдите кратность каждого значения в обоих мешках; одного несовпадения достаточно, чтобы мешки были разными.

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

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

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

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

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