Склеивание мешков цепочек

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

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

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

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

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

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

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

Нельзя соединять только элементы с одинаковыми номерами, потому что номер не задаёт особого правила выбора. Например, у мешков {«а», «б»} и {«1», «2»} нужны пары «а» с «1», «а» с «2», «б» с «1» и «б» с «2». Если взять только две пары по позициям, два допустимых результата потеряются. Полный перебор нужен именно потому, что любой элемент одного мешка может сочетаться с любым элементом другого.

Повторы в исходных мешках влияют на кратность результата. Если цепочка «а» записана в первом мешке дважды, каждая её копия образует отдельную пару с каждым элементом второго мешка. Поэтому при склеивании {«а», «а»} и {«1», «1», «2»} результат «а1» появляется четыре раза, а «а2» — два раза. Записи одинаковых результатов не удаляют, иначе потеряется информация о числе породивших их пар.

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

Склеивание мешков цепочек

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

Разбор задач

Склеивание двух цепочек

Условие. Склеить цепочки «ко» и «т». Нужно определить, какая из них первая, и убрать мысленную границу между частями. Разделитель между цепочками в результате не записывается.

1. Первой берём цепочку «ко».
2. К её концу приписываем «т».
3. Читаем получившуюся цепочку слева направо.

Ответ: «кот».

Склеивание двух мешков

Условие. Склеить мешки {«а», «б»} и {«1», «2»}. Нужно получить результат для каждой пары, а не только для элементов, стоящих на одинаковых местах. Порядок мешков уже задан условием.

1. Для «а» составляем пары с «1» и «2»: получаем «а1» и «а2».
2. Для «б» снова перебираем весь второй мешок: получаем «б1» и «б2».
3. Объединяем все полученные цепочки в мешок результата.

Ответ: {«а1», «а2», «б1», «б2»}.

Учёт повторов

Условие. Склеить мешки {«а», «а»} и {«1», «1», «2»} и указать кратность каждой цепочки. Две записи «а» считаются двумя элементами, как и две записи «1». Поэтому одинаковый текст результата может появиться от разных пар.

1. Первая «а» даёт «а1», «а1», «а2».
2. Вторая «а» даёт ещё «а1», «а1», «а2».
3. Собираем одинаковые результаты и считаем их появления: «а1» встретилась четыре раза, «а2» — два раза.

Ответ: «а1» имеет кратность 4, «а2» — кратность 2; результат можно записать как {«а1», «а1», «а1», «а1», «а2», «а2»}.

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

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

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

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

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

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

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

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

Операция пригодится при построении новых наборов цепочек и описании действий над ними. Перебор всех пар развивает навык систематического поиска вариантов. Позже такая идея встречается при составлении комбинаций и обработке наборов данных.

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

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