Математика · объяснение и практика

Как восстановить множество по дельте изменений и отменить повторные переключения

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

Синяя и оранжевая половины складываются в целый круг.

В теме Множества, отношения и математическая логика · Учебная карта

В маршруте Множества, отношения и мощности · 10 тем

Главная мысль

Если дельта D задаёт элементы, чьё присутствие переключается, новое множество равно B=A△D. Прежнее состояние восстанавливается тем же действием: A=B△D. Для нескольких таких дельт складывают их симметрической разностью; два одинаковых переключения каждого элемента взаимно отменяются.

Дельта описывает переключение, а не новое полное состояние

Зададим точную модель: каждый номер либо включён в набор, либо отсутствует. Дельта содержит номера, у которых этот признак нужно изменить. Присутствующий номер удаляется, отсутствующий добавляется. Такое переключение выражается симметрической разностью. Это отдельный договор о значении данных, а не свойство любого списка с названием «изменения».

Пусть исходно A={1,4,7}, а D={4,6}. Применив дельту, получаем B={1,6,7}: четвёрка исчезла, шестёрка появилась. Размер набора остался равным трём, хотя само множество изменилось. Поэтому одно сравнение размеров не восстанавливает изменения. Для поставленной задачи сохраняют конкретные номера и правило их переключения.

Восстановить исходный набор тем же действием

При повторном переключении всех номеров D каждый возвращается в прежнее состояние. Элементы вне D оба раза не затронуты. Отсюда (A△D)△D=A. В нашем примере {1,6,7}△{4,6} снова даёт {1,4,7}. Направление добавления или удаления не требуется хранить отдельно: его определяет известное текущее состояние.

Если последовательно применены D₁ и D₂, конечное состояние равно A△D₁△D₂. Для восстановления можно применить обе дельты ещё раз. Их общая дельта равна D₁△D₂, а не обычному объединению. Общий номер переключается дважды и потому не должен оставаться в итоговом списке переключений.

Пример

Пусть A={1,2}, D₁={2,4}, D₂={4,5}. Найдите общее изменение и конечный набор.

Общая дельта равна {2,5}: номер4 встретился дважды и отменился. По шагам получаем {1,4}, затем {1,5}. Сразу A△{2,5} даёт то же {1,5}. Номер4 нельзя оставить как итоговое добавление.

Проверить условия обратимости модели

Доказательство можно провести для каждого номера отдельно: ноль обозначает отсутствие, единица — присутствие. Переключение меняет одно значение на другое, а два переключения возвращают исходное. Поэтому при известной полной дельте новое состояние однозначно определяет старое. Ассоциативность позволяет группировать эти операции; порядок не влияет на окончательное множество в данной модели.

Если сообщение содержит новое полное состояние вместо дельты, повторное применение уже не обязано отменять действие. Команды «добавить» или «удалить» тоже отличаются от переключения. Например, повтор команды добавления не удаляет номер обратно. Для списков с кратностями нужна иная модель. Перед восстановлением следует установить смысл сообщения, полноту записей и одинаковые обозначения номеров, иначе красивая формула решит другую задачу.

От чтения к действию

А теперь — вы

Конечное множество B={2,5}. Перед этим к неизвестному исходному набору последовательно применили переключающие дельты D₁={1,2} и D₂={2,4}. Каким был исходный набор?

Частые вопросы

Можно ли заменить общую дельту объединением списков?

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

Достаточно знать только число переключённых номеров?

Нет. Разные дельты одинакового размера дают разные исходные наборы. Для точного восстановления нужны сами элементы дельты и известное текущее состояние.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться