如何计算将一个排序顺序转换为另一个排序顺序的绝对最小变化量？

Question

目标

如何编码描述如何使用可能的最小字节数将静态列表从一个订单重新排序到另一个订单的数据？

原始动机

最初,在使用昂贵的卫星通信来处理传感器数据的问题时,出现了这个问题.一台设备列出了他们正在监控的大约1,000个传感器.传感器列表无法更改.每个传感器都有一个唯一的ID.所有数据都在内部记录以进行最终分析,最终用户每天唯一需要的是哪个传感器以哪种顺序触发.

整个项目都被废弃,但这个问题似乎太有趣了,不容忽视.此前我还谈到了"交换",因为我正在考虑排序算法,但实际上它是整体​​顺序很重要,达到该顺序所需的步骤可能无关紧要.

如何订购数据

在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

假设

• 起始列表和结束列表由完全相同的项目组成
• 每个传感器都有一个唯一的id(32位整数)
• 列表的大小约为1,000个项目
• 每个传感器可能每分钟发射多次,或者根本不发射数天
• 只需要中继ID排序顺序的更改.
• 用于计算最佳解决方案的计算资源是便宜/无限的
• 数据成本很高,大约每千字节一美元.
• 数据只能以整个字节(八位字节)为增量发送
• 第0天订单由发件人和收件人知道
• 现在假设系统功能完美,不需要进行错误检查

正如我所说,项目/硬件不再如此,现在这只是一个学术问题.

挑战!

定义一个编码器

• 鉴于A. Day N排序顺序
• 鉴于B. Day N + 1排序
• 返回C.一个字节集合,描述如何使用尽可能少的字节数将A转换为B.

定义解码器

• 鉴于A. Day N排序顺序
• 给定B.字节集合
• 返回C. Day N + 1排序

大家好玩.

Answer 1

作为一个学术问题，一种方法是查看 Knuth 的《计算机编程艺术》第二卷的算法 P 第 3.3.2 节，该算法将 N 个对象上的每个排列映射为 0 到 N!-1 之间的整数。如果每个可能的排列在任何时候都有相同的可能性，那么您能做的最好的事情就是计算并传输这个（多精度）整数。实际上，给每个传感器一个 10 位数字，然后将这些 10 位数字打包，这样您就可以将 4 个数字打包到每个 5 字节的块中，效果也差不多。

基于 diff 或现成压缩的方案利用了并非所有排列都同样可能的知识。您可能根据设备对此有所了解，或者您可以通过查看以前的数据来了解是否属于这种情况。如果有效的话就好了。在某些使用传感器和卫星的情况下，您可能需要担心罕见的例外情况，即您的压缩方案会出现最坏的情况，并且您突然需要传输的数据比您预期的要多。