如何计算将一个sortorder转换为另一个sortorder的绝对最小更改量？

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

假设

开始列表和结束列表由完全相同的项目集组成，每个传感器都有一个唯一的id (32位整数) relayed.

• Computation

• ，该列表的大小将大约为1,000项

• ，每个传感器可能每分钟触发多次或根本不触发几天--

H 118只有ID排序顺序的更改需要成为unlimited

• Data资源，以确定最优的解决方案是廉价的/unlimited

• Data成本昂贵，大约每千字节1美元。

• 数据只能以全字节(八进制)递增(

• )方式发送。发送方和接收方都知道第0天的顺序是从

• 开始的，因为现在假定系统功能完美，不需要进行错误检查(

)。

正如我所说的，项目/硬件已经不复存在，所以这现在只是一个学术问题。

挑战！

定义编码器

• 给出A.日期N排序顺序
• 给定B. Day N+1排序顺序
• 返回C.描述如何使用尽可能少的字节数

将A转换为B的字节集合。

定义解码器

• 给出了A. Day N排序顺序
• 给定B.字节的集合
• 返回C天N+1排序顺序

大家玩得开心。

Answer 1

作为一个学术问题，一种方法是研究Knuth的第二卷的算法P节3.3.2 -计算机编程艺术，它将N个对象上的每一个置换映射为0到N-1之间的整数。如果每个可能的排列在任何时候都是相同的，那么你能做的最好的就是计算和传输这个(多精度)整数。在实践中，给每个传感器一个10位的数字，然后将这10位数字打包起来，例如，将4个数字打包到每个5字节的块中就差不多了。

基于差异或现成压缩的方案利用的知识是，并不是所有的排列都是相同的。根据设备，您可能对此有了解，或者通过查看以前的数据可以看出情况是否如此。如果能用的话。在有些情况下，有传感器和卫星，你可能想担心罕见的例外，当你得到最坏的情况下，你的压缩方案，你突然有更多的数据要发送超过你的预期。