如何计算改变的绝对最小量的一个排序顺序转换成另一种？(How to compute the abso

目标

如何编码，描述了如何重新排序从一阶的静态列表使用可能的最小数据量的另一种顺序的数据？

我有一种感觉，有一种算法或计算机科学方面的术语，这将帮助我，但现在我也坚持对这个问题要弄清楚看它的其他方式。

背景动机

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

在一天的开始，用户被授予项目的名单，他们走出去的领域，做的东西，但最终的结果是或多或少地以不同的顺序排序的项目相同的列表。 还有其他的数据，但它并不重要这个问题。

现在，我发回发生的所有动作的记录，并在顺序播放他们回来。 随着用户获得舒适与移动记录列表开始接近刚刚发回的所有项目本身的大小，并经常在撤销前几次的动作结果的某种组合的系统。

假设

• 在首发名单和结束名单是由完全相同的一组项目的
• 每一个项目都有一个唯一的ID（32位整数）
• 每一个项目都有一个唯一的排序奥德（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的使用可能的最小数据量的顺序？

作为一种好奇心是可以证明有一个解决方案是最优的？

更新

一位同事指出，“交换”未必是认为它正确的方式。 您还可以发送一个项目，其更多的是比移动交换列表的顶部或底部。 一个交换然后变成的两个动作的组合。

感谢您的指针。 到目前为止，我没有看到一个保证最佳的解决方案。 加上问题恰恰变化不大。

如果我不能证明任何单一的方法产生最好的结果，那么我会利用一切方法，找出解决的办法，并发送回该解决方案有一个小头标明所使用的方法。 请提出解决办法，虽然我会更新我的研究这个问题。

感谢大家！

Answer 1:

事物的一部分：

列表的重新排序称为排列。 每个排列可以分成一组环的 ，与需要N个元素（N - 1）的每个循环互换。 例如

1，2，3，4，5，6 - > 3，2，4，1，6,5

这可以分成1 - 4 - 3（需要2个互换）2 - 2（0互换）5 - 6（1个交换）

要找到解决的办法，你可以随便挑任何元素在错误的位置，并把它放在自己的位置。

细节的一部分：

当然，你可以用较小的数据类型，RLE或一些其他的编码算法等。

非常理论化但不实用的部分。

N个序列的所有排列可以按字典顺序排列 ，并从0到一个号码（N！ - 1）是足以代表序列。 所以，理论上最好的答案是：计算置换的指标，其转移，重新创建该索引的排列。

Answer 2:

你需要的是对列表进行排序所需的置换。 您可以通过构建指数列表从0到n，然后排序与项目的相应索引进行比较的自定义比较函数列表得到这个。 例如，在Python：

perm = sorted(range(len(l)), key=lambda x:l[x])

然后，您可以发送“烫发”通过该连接，并用它来获得排序列表：

for x in perm:
  print perm[x]

作为进一步的优化，如果大多数元素保持不变，置换将是高度可压缩的 - 或者通过使用常规的压缩或通过使用像差值变换（例如，存储每个元素作为从先前元素的差，而不是它的绝对值）， 移动到前和运行长度编码 。

Answer 3:

我不知道该分析互换让你什么; 就像你说的，他们可以撤消对方，并造成混乱的结果。

我认为，最好的选择是确定，在重新排序列表，该列表未重新排序相对于原来的名单中，段，即使他们在新的地点开始。 在您的例子，这是从30到60。因此，在一种运行长度编码的部分，我会发回描述了位置和长度分段映射。

同样，使用您的数据。例如：下令开始索引列表，长度：

{（9,1），（3,4），（1,1），（8,1），（7,1），（2,1）}

好像你可以发送回信息的最小量。 数据的可压缩性取决于共同持有的段的数量和大小。

（编辑）事实上，它发生，我认为有一些将要数据集合，其中一个交换清单会更短，如果掉期的数量较少。 但也有可能会是一些割接点运行长度编码越办越好; 在这种情况下，我会说同时计算并选择较小的一个。

Answer 4:

如果你真正想将数据通过线路的每一位最小化，你如何传送你的数据？ 例如，你在某种程度上压缩了吗？ 使用排序顺序一个32位的数字可能是矫枉过正，如果你只有几千元的物品。 16位让你65000项一半$$$。 这同样适用于唯一的ID。

Answer 5:

另一种可能的解决方案，而忽略你的数据结构...

发送对已更改的项目一套IDS /索引（如果它是一个完全随机的稀疏子集，只是列出），并描述该子集的重新排序的排列数。 置换数量将需要一个大的整数表示 - 大小应该是成正比的log（n！），其中n是改变项目的数量。

置换数从一个排列阵列当然，定义，但是可以在解码时能够避免这个细节。 关键是要编码的排列数目，使得，一旦你交换正确的第一个项目到所述第一狭槽，还可以派生一个新的置换数是用于阵列的尾部正确。

那是...

while not empty(indexes)
  item-to-swap := permutation-no remainder len(indexes)
  permutation-no := permutation-no div len(indexes)
  if item-to-swap != 0 : swap slot[indexes[0]], slot[indexes[item-to-swap]]
  indexes := tail(indexes)

！该=需要0检查，即使需要在开始改变所有项目 - 一个项目可能会被交换向上进入它的早期循环中正确的位置。

这并不试图优化掉期的数量 - 项目可被换入向下它的正确位置之前被交换向上几次。 这就是说，排列号码可能是用于阵列的随机置换的最佳空间表示。 鉴于您的排列不仅影响了全阵列的一小部分，使用该子集让有很大的意义较小的排列数。

Answer 6:

速战速决可能是使用一个佐布里斯特哈希被发现的情况下你回到先前的订单。 也就是说，每个交换后，计算基于到达排列的哈希值。 每个哈希值映射到迄今发现的特定置换掉期最短的序列。

这可以很容易地带着几分试探性搜索的延伸 - 在佐布里斯特哈希被发明，以此来优化博弈树搜索。

这容易给人一种严格的下界掉期的数量，当然 - 这不是他们所要求的位置的项目数。 这是否下界实际上是可以实现的，虽然是一个比较棘手的问题。

Answer 7:

假如说：

• 你可以把你的基本系统上的两个现场设备的原始和最终数据的副本，
• 当你谈论掉期，你的意思是列表中的两个项目彼此交换

你最好的解决方案可能是：

而不是保持所有你要做的，因为他们进行的，在一天结束的时候比较你的起止数据，然后生成你需要进行改变的掉期互换的列表。 这将忽略保持不变列表中的任何位置，即使他们只是不变，因为一系列的掉期“毁掉”一些变化。 如果你有你的数据采取的形式是a,b,a,b,...其中a告诉你下一个元素的索引中他们以相同的顺序离开， b告诉你项目的索引与交换它。

因为你只是做掉，而不是漂移，你应该很少有像你的样本数据数据，其中30，40和50都以相同的顺序，但在一个稍微不同的位置结束。 由于掉期交易的数量将1/4和1/10列表中的原始项目的数量之间，你通常有你的数据在两个相同的顺序和相同的位置，它是在原来的一大块。 让我们假设下面的掉期提出：

1 <-> 9
4 <-> 2
5 <-> 2 

结果列表将是：

 1. 90                   
 2. 50                  
 3. 30                      
 4. 20                       
 5. 40                      
 6. 60                       
 7. 70                       
 8. 80                       
 9. 10                        

所以变化数据可以表示为：

 1,9,2,4,4,5

这是只有六个值，可以表示为16位数字（假设你会不会在你的初始列表超过16,000项）。 因此，每个“有效”的交换可以用一个单一的32位的数字来表示。 而且，由于实际交换的数量一般为1/5至1/2的原始列表的大小，你会最终10％和20％，在原始列表中的数据之间发送通过线路（或更少，因为如果一些那些互换撤消彼此）的“有效”互换的数量可以更少。

Answer 8:

正如彼得说，这将是理想的，以尽量减少每个整数的大小 - 其实，你可以不用将限制对项目的数量。 可变字节编码是通过仅使用字节的必要数量的压缩整数的序列的一种方式。 这样做的最常用的方法是保留一个位在每个字节，表示该字节是否在当前列表项的最后一个。

这可能是先用增量编码有用。 这就是你存储整数自己整数之间的差异 ，而不是-这意味着他们最终压缩可变字节的更好。 当然，整数存储（也许是项目的ID被改变，你的情况），就必须先排序，但似乎并不像它会成为你的问题。

文章来源: How to compute the absolute minimum amount of changes to convert one sortorder into another?