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

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

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

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

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

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

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

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

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

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

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

Сравнение одинаковых и разных мешков

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

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

Разбор задач

Задача 1. Определить, одинаковы ли мешки {красный, синий, синий} и {синий, красный, синий}. Нужно решить, влияет ли перестановка цветов на состав и совпадают ли повторения.

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

Ответ: мешки одинаковы. В каждом из них один красный и два синих элемента.

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

1. В первом мешке число 2 встречается два раза, число 5 — один раз, число 7 — один раз.
2. Во втором мешке число 2 встречается один раз, число 5 — два раза, число 7 — один раз.
3. Количество двоек и пятёрок различается, значит, составы не совпадают.

Ответ: мешки разные. Например, двойка встречается в них соответственно два и один раз.

Задача 3. Из мешка {а, а, б, в, в} убрать или добавить элементы так, чтобы он стал одинаковым с мешком {в, а, в, б, а}. Удобно не переставлять символы, а составить таблицу количеств.

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

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

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

Ошибка 1. Считать мешки разными из-за разного порядка элементов. Так происходит, когда свойство последовательности переносят на мешок. Проверьте себя: переставьте элементы мысленно и сравните количества.

Ошибка 2. Не учитывать повторяющиеся элементы. Ученик видит только виды объектов и забывает их пересчитать. Составьте для каждого элемента отдельную пару чисел — это сразу покажет различие.

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

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

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

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

Связь с математикой проявляется в подсчёте повторений и группировке одинаковых объектов. Такие действия превращают сравнение мешков в понятную таблицу количеств.

Дальше идея мешка пригодится при описании алгоритмов обработки наборов данных, подсчёте частот и работе с таблицами. Например, можно определять, сколько раз встречается каждое слово или число.

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

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