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

Цель

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

Исходная мотивация

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

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

Как данные были заказаны

В терминах 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 бита)
• Размер списка будет приблизительно 1 000 объектов
• Каждый датчики может стрелять многократно в минуту или нисколько в течение многих дней
• Только изменение в идентификационном порядке сортировки должно быть передано.
• Ресурсы вычисления для расчета оптимальных решений дешевы / неограниченный
• Затраты данных являются дорогими, примерно доллар на килобайт.
• Данные могли только быть отправлены как целый байт (октет) инкременты
• День 0 порядков, как известен отправитель и получатель, запускается с
• На данный момент примите системные функции отлично, и никакая проверка ошибок не требуется

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

Проблема!

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

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

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

• Данный A. День N порядок сортировки
• Данный B. набор байтов
• Возвратите C. День N + 1 порядок сортировки

Весело проведите время все.