algorithm - 如何计算将一个排序顺序转换为另一个排序顺序的绝对最小更改量？

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 排序顺序的更改。
• 用于计算最佳解决方案的计算资源很便宜/没有限制
• 数据成本很高，大约每千字节 1 美元。
• 数据只能以整字节(八位字节)递增的形式发送
• 发件人和收件人都知道第 0 天订单
• 现在假设系统功能完美并且不需要错误检查

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

挑战!

定义编码器

• 给定第 A 天的排序顺序
• 给定 B. 第 N + 1 天排序
• 返回 C. 描述如何使用尽可能少的字节数将 A 转换为 B 的字节集合

定义解码器

• 给定第 A 天的排序顺序
• 给定 B. 一组字节
• 返回 C. 第 N + 1 天排序

祝大家玩得开心。

Answer 1

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

基于差异或现成压缩的方案利用并非所有排列的可能性都相同的知识。您可能根据设备知道这一点，或者您可以通过查看以前的数据来了解是否属于这种情况。如果有效，那很好。在某些使用传感器和卫星的情况下，您可能需要担心罕见的异常情况，即您的压缩方案出现最坏的情况，并且您突然要传输的数据比您预料的要多。