如何计算变动的绝对最低金额将一个排序顺序为另一种？ [英] How to compute the absolute minimum amount of changes to convert one sortorder into another?

问题描述

目标

如何连接code，它描述了如何从一个以另一种顺序使用数据的最低金额重新排序静态列表中的数据可能吗？

How to encode the data that describes how to re-order a static list from a one order to another order using the minimum amount of data possible?

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

I have a feeling there is an algorithm or computer science term that will help me but right now I'm too stuck on the problem to figure out other ways of looking at it.

背景动机

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

I'm have a program that is deployed to a remote location where all communication is via an intermittent incredibly expensive satellite connection. It's a slight exaggeration, but data costs are close to a dollar per kilobyte and can only happen a few times per day.

目前的用户被授予的项目的列表的一天的开始，他们出门在现场和做的东西，但最终的结果是或多或少项排序的顺序不同的相同的列表。还有其他的数据，但它并不重要这个问题。

At the start of the day the users are given a list of items, they go out in the field and do stuff but the end result is more or less the same list of items sorted in a different order. There's other data but it's not important to this problem.

现在，我发回的所有发生的动作记录和播放他们回来才能。由于用户获得舒适与系统的移动记录列表开始接近刚发回所有项目本身的尺寸，并常常举动结果撤消previous那些某种组合。

Right now I'm sending back a record of all the moves that occur and playing them back in order. As users get comfortable with the system the list of move records is starting to approach the size of just sending back all the items themselves, and often some combination of moves results in undoing previous ones.

假设

• 的首发名单和结束列表是由完全相同的一组项目的
• 在每个项目都有一个唯一的ID（32位整数）
• 在每个项目都有一个唯一的排序奥德（​​32位整数）
• 用户将有几百到上千元或更多项的列表
• 用户一般会重新整理这些项目的约100天
• 在可以被检测到更改的顺序移动的一个项目，一个新的列表中的位置
• 在一些动作可以撤销previous那些
• 计算资源盘算最优解是便宜/无限
• 传输时间是昂贵的
• 发回的变化数据比发送回整个列表便宜

• The starting list and ending list is composed of the exact same set of items
• Each item has a unique id (32 bit integer)
• Each item has a unique sort oder (32 bit integer)
• User will have a list of several hundreds to a thousand or more items
• User will generally re-order about 100 of those items in a day
• Changes to the order can be detected moving an item to a new position in the list
• Some "moves" may undo previous ones
• Computation resources for figuring optimal solutions is cheap / unlimited
• Transmission time is expensive
• Sending back the change data is cheaper than sending the back the whole list

最简单的数据结构

有关解决该问题的目的，假设下列数据结构都可以。

For the purposes of solving this problem assume the following data structures are available.

• 在列表项
  • ITEM_ID
  • 请将sort_order
  • ListItem
    • item_id
    • sort_order
    • item_a_id
    • new_a_position

    下面是一个例子列表。在每个列表中的项目是相同的。请注意，尽管只有少数的项目发生了变化，每一个项目的ID有一个新的排序顺序，所以你不能只是发回新的ITEM_ID / sort_order_id对。

    Here is an example list. The items in each list are the same. Notice that even though only a few of the items have changed, every single item id has a new sort order so you can't just send back new item_id/sort_order_id pairs.

    **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
    

    我如何连接code。使用数据的最低金额为1列出的顺序转换所需的变革，为表2的顺序可能吗？

    How do I encode the changes required to convert the order of List 1, into the order of List 2 using the minimum amount of data possible?

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

    As a curiosity is it possible to prove that there is a solution is optimal?

    更新

    一个同事指出，交换可能不会想到它正确的方式。还可以发送一个项目以哪个更一动比的交换列表的顶部或底部。一个交换就变成了两个动作的组合。

    A co-worker pointed out that "swap" may not be correct way to think of it. You can also send an item to the top or bottom of the list which is more of a move than a swap. A swap then becomes a combination of two moves.

    感谢您的指点。到目前为止，我没有看到一个保证最佳的解决方案。加上问题只是改变了一点点。

    Thanks for the pointers. So far I don't see a guaranteed optimal solution. Plus the problem just changed a little.

    如果我不能证明任何单一的方法产生最好的结果，那么我会想出一个解决方案，利用一切方法和发回的解决方案，一个小头，表示使用的方法。请提出解决办法，虽然，我会更新这个问题与我的研究工作。

    If I can't prove any single method produces the best result then I'll figure out a solution using every method and send back that solution with a small header indicating the method used. Keep suggesting solutions though and I'll update this question with my research.

    谢谢大家！

    推荐答案

    算法中的一部分：

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

    A reordering of a list is called permutation. Each permutation can be split into a set of loops, with each loop of N elements requiring (N - 1) swaps. For example

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

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

    此可分割成 1 - 4 - 3（需要2个掉期） 2 - 2（0互换） 5 - 6（1互换）

    This can be split into 1 - 4 - 3 (requires 2 swaps) 2 - 2 (0 swaps) 5 - 6 (1 swap)

    要发现你可以随便挑任何元素在错误的位置，并把它放在了一个解决方案。

    To find a solution you can just pick any element at a wrong position and put it on its place.

    详细信息部分：

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

    Of course, you can use smaller data types, RLE or some other encoding algorithms and so on.

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

    N个数序列的所有排列可以字典顺序有序和从0 1号至（N！ - 1）就足以重新present序列。因此，从理论上最好的答案是：计算置换的指标，将其传送，重新排列由指数

    All permutations of a sequence of N numbers can be lexicographically ordered, and one number from 0 to (N! - 1) is enough to represent the sequence. So, theoretically best answer is: compute the index of the permutation, transfer it, recreate the permutation by that index.

    这篇关于如何计算变动的绝对最低金额将一个排序顺序为另一种？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！