Одинаковые мешки. Разные мешки

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

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

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

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

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

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

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

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

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

Мешки с одинаковыми видами объектов, но разными повторами, являются разными. Например, в {а, а, б, в} и {а, б, б, в} представлены одни и те же объекты а, б и в. Однако в первом мешке а встречается дважды, а во втором — один раз; у б наблюдается обратное. Достаточно найти хотя бы один объект с несовпадающей кратностью, чтобы сделать вывод о различии мешков.

Чтобы сравнивать длинные записи, можно упорядочить элементы одинаковым способом или составить перечень объектов с указанием их кратностей. В первом случае одинаковые элементы ставят рядом, поэтому повторения легче пересчитать. Во втором записывают, например: а — 2, б — 1, в — 2. Затем значения сопоставляют для каждого объекта, и порядок исходной записи уже не мешает проверке.

Как сравнивать мешки

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

Разбор задач

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

1. В первом мешке есть а, б и в, каждый встречается один раз.
2. Во втором мешке представлены те же а, б и в, также по одному разу.
3. Кратность каждого объекта совпадает, значит, различие порядка не влияет на результат.

Ответ: мешки одинаковы. Их перечни отличаются только последовательностью элементов.

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

1. В первом мешке а встречается два раза, б — один раз, в — один раз.
2. Во втором мешке а тоже встречается два раза, б — один раз, в — один раз.
3. Кратности всех объектов совпали; порядок перечисления при сравнении не учитывается.

Ответ: мешки одинаковы, потому что у каждого объекта в них одинаковая кратность.

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

1. В первом мешке а встречается два раза, б — один раз, в — два раза.
2. Во втором мешке а встречается один раз, б — два раза, в — два раза.
3. У а и б кратности не совпадают, хотя в каждом мешке всего по пять элементов.

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

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

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

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

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

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

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

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

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

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

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