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

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. n天排序顺序
• 鉴于B.日N + 1排序次序
• 返回C.字节的集合，描述如何使用可能的字节数最少的甲转换为乙

定义解码器

• 鉴于A. n天排序顺序
• 鉴于B.的集合字节
• 返回C.天N + 1排序顺序

玩得开心大家。

Answer 1

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

基于差异或现成压缩的方案利用了并非所有排列的可能性相同的知识。您可能根据设备了解此情况，或者通过查看以前的数据来查看是否属实。很好，如果它的工作。在一些使用传感器和卫星的情况下，您可能需要担心罕见的例外情况，如果您的压缩方案出现最差情况，并且突然有更多的数据传输超过您的议价范围。