相关疑难解决方法(0)

目标

如何使用尽可能少的数据对描述如何将静态列表从一个订单重新排序到另一个订单的数据进行编码？

我有一种感觉,有一个算法或计算机科学术语可以帮助我,但现在我太过坚持问题,找出其他方法来看待它.

背景动机

我有一个部署到远程位置的程序,所有通信都是通过间歇性的极其昂贵的卫星连接进行的.这有点夸张,但数据成本接近每千字节一美元,每天只能发生几次.

在一天开始时,向用户提供项目列表,他们在现场外出并做东西,但最终结果或多或少是以不同顺序排序的相同项目列表.还有其他数据,但这对这个问题并不重要.

现在我发回所有发生的动作的记录并按顺序播放它们.当用户对系统感到满意时,移动记录列表开始接近仅发回所有项目的大小,并且通常移动的某些组合导致撤消先前的移动记录.

假设

• 起始列表和结束列表由完全相同的项目组成
• 每个项目都有一个唯一的id(32位整数)
• 每个项目都有一个唯一的排序oder(32位整数)
• 用户将拥有数百至数千或更多项目的列表
• 用户通常会在一天内重新订购约100件商品
• 可以检测到对订单的更改将项目移动到列表中的新位置
• 一些"移动"可能会撤消之前的移动
• 用于计算最佳解决方案的计算资源是便宜/无限的
• 传输时间很昂贵
• 发回更改数据比发回整个列表便宜

最简单的数据结构

出于解决此问题的目的,假设以下数据结构可用.

• 项目清单
  • ITEM_ID
  • 排序
• MoveRecord
  • item_a_id
  • new_a_position

这是一个示例列表.每个列表中的项目是相同的.请注意,即使只有少数项目已更改,但每个项目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的顺序所需的更改？

好奇心是否有可能证明 …