Как вычислить абсолютное минимальное количество изменений для преобразования одного сортировщика в другой?

Question

Цель

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

Оригинальная мотивация

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

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

Как были упорядочены данные

В терминах SQL вы можете думать об этом так.

**Initial Load**

create table sensor ( id int, last_detected datetime, other stuff )
-- fill table with ids of all sensors for this location

Day 0: Select ID from Sensor order by id
  (initially data is sorted by the sensor.id because its a known value)

Day 1: Select ID from Sensor order by last_detected
Day 2: Select ID from Sensor order by last_detected
Day 3: Select ID from Sensor order by last_detected

Предположения

• Начальный список и конечный список состоят из одного и того же набора элементов
• Каждый датчик имеет уникальный идентификатор (32-разрядное целое число)
• Размер списка будет примерно 1000 наименований
• Каждый датчик может срабатывать несколько раз в минуту или не срабатывать в течение нескольких дней
• Необходимо передать только изменение порядка сортировки идентификаторов.
• Ресурсы для определения оптимальных решений дешевы / неограниченны
• Стоимость данных высока, примерно доллар за килобайт.
• Данные могут быть отправлены только как целые байтовые (октетные) приращения
• Отправитель и получатель знают, что заказ в День 0 начинается с
• На данный момент предположим, что система функционирует отлично и проверка ошибок не требуется

Как я уже сказал, проект / оборудование больше не существует, так что теперь это просто академическая проблема.

Испытание!

Определить кодировщик

• Учитывая порядок сортировки по дню N
• Дано B. День N + 1 порядок сортировки
• Возвращает C. набор байтов, которые описывают, как преобразовать A в B, используя наименьшее возможное количество байтов

Определить декодер

• Учитывая порядок сортировки A. Day N
• С учетом Б. набора байтов
• Возврат C. День N + 1 порядок сортировки

Веселятся все.

Answer 1

В качестве академической проблемы одним из подходов было бы взглянуть на раздел 3.3.2 Алгоритма Р из II тома Кнута - искусство компьютерного программирования, которое отображает каждую перестановку N объектов в целое число от 0 до N! -1. Если каждая возможная перестановка одинаково вероятна в любое время, тогда лучшее, что вы можете сделать, - это вычислить и передать это (с высокой точностью) целое число. На практике, давая каждому датчику 10-битное число, а затем упаковывая эти 10-битные числа, вы получите, например, 4 числа, упакованные в каждый 5-байтовый фрагмент, будут работать почти так же хорошо.

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