Goal
如何使用尽可能少的数据对描述如何将静态列表从一个顺序重新排序到另一个顺序的数据进行编码?
我有一种感觉,有一种算法或计算机科学术语可以帮助我,但现在我太专注于这个问题,无法找出其他看待它的方法。
背景动机
我有一个程序部署到一个远程位置,所有通信都是通过间歇性的极其昂贵的卫星连接进行的。这有点夸张,但数据成本接近每千字节一美元,而且每天只能发生几次。
在一天开始时,用户会收到一个项目列表,他们到现场做一些事情,但最终结果或多或少是按不同顺序排序的相同项目列表。还有其他数据,但对这个问题来说并不重要。
现在我正在发回所有发生的动作的记录并按顺序回放它们。随着用户对系统的熟悉,移动记录列表的大小开始接近仅发回所有项目本身的大小,并且通常某些移动组合会导致撤消以前的记录。
假设
- 起始列表和结束列表由完全相同的一组项目组成
- 每个项目都有一个唯一的 id(32 位整数)
- 每个项目都有一个唯一的排序顺序(32 位整数)
- 用户将拥有数百到一千甚至更多项目的列表
- 用户通常会在一天内重新订购其中大约 100 件商品
- 可以检测到顺序的更改,将项目移动到列表中的新位置
- 有些“举动”可能会撤销之前的举动
- 用于找出最佳解决方案的计算资源很便宜/不受限制
- 传输时间昂贵
- 发回更改数据比发回整个列表更便宜
最简单的数据结构
为了解决这个问题,假设以下数据结构可用。
这是一个示例列表。每个列表中的项目都是相同的。请注意,尽管只有少数项目发生了更改,但每个项目 id 都有一个新的排序顺序,因此您不能只发回新的 item_id/sort_order_id 对。
**List 1: Original List** **List 2: Re-ordered List**
order - id order - id
1. 10 1. 90
2. 20 2. 30
3. 30 3. 40
4. 40 4. 50
5. 50 5. 60
6. 60 6. 10
7. 70 7. 80
8. 80 8. 70
9. 90 9. 20
如何使用尽可能少的数据量对将列表 1 的顺序转换为列表 2 的顺序所需的更改进行编码?
出于好奇,有可能prove那有一个解决方案是最优的吗?
Update
一位同事指出,“交换”可能不是正确的理解方式。您还可以将项目发送到列表的顶部或底部,这更像是移动而不是交换。然后交换就变成了两个动作的组合。
感谢您的指点。到目前为止,我还没有看到有保证的最佳解决方案。而且问题只是发生了一点变化。
如果我无法证明任何一种方法都能产生最佳结果,那么我将使用每种方法找出一个解决方案,并将该解决方案发回,并用一个小标头指示所使用的方法。不过,请继续提出解决方案,我将用我的研究更新这个问题。
感谢大家!