基于前次排序进行排序

Question

我正在尝试根据“排序映射”对ID列表进行排序，该映射是一个由（ID1，ID2，时间戳）元组组成的数组，确定哪些ID应在其他ID之前排序。以下是规则：

- ID1应在ID2之前排序。 - 时间戳可用于打破平局，新时间戳胜过旧时间戳。例如，给定排序键（C，A，1/1/1900），（C，B，1/1/2000），则B在A之前排序。 - 可能存在循环，例如（A，B，1/1/1950），（B，C，1/1/1980），（C，A，1/1/1900）。可以使用时间戳来打破循环，并将循环中时间戳较早的记录从排序映射中删除，直到循环消失。 - 如果ID不在排序映射中，则将其排序在任何出现在排序映射中的ID之后。

例如：给定排序映射（C，A，1/1/1900），（C，B，1/1/2000）和要排序的列表（A，B，C，D），排序后的输出将为（C，B，A，D）。

我被转换这些规则为算法所困惑。以下是我目前的进展：

1. 从数据库中获取最新的排序映射。我将最多为每个唯一ID对获取一条记录。
2. 从排序映射中移除循环。如何？或者忽略步骤4中的循环是否更容易？
3. 在内存中转换排序映射以实现最佳性能。例如，构建一个哈希表，其中键是排序映射中的每个唯一ID，以便可以快速查找包含特定ID的所有排序映射行。
4. 使用通用的二进制排序库对我的ID数组进行排序，使用自定义比较函数接受任何两个ID ID1和ID2参数。比较函数：

   a. 使用步骤＃3中的哈希表查找包含ID1或ID2的所有排序映射条目。

   b. 如果排序映射中已经有包含ID1和ID2的记录，则停止-我们知道哪个应该排在前面！

   c. 如果在排序映射中既没有找到ID1也没有找到ID2，则它们是平局。返回确定性的任意结果（例如，ID较小的获胜）。

   d. 如果一个ID在排序映射中，但另一个ID不在，则停止。找到的应该首先排序。

   e. 如果我们到达这里，那么两个ID都在排序映射中，但是在排序映射中没有直接比较可用。 现在怎么办？

性能不是一个大问题，因为排序映射的最大大小小于20K行，而要排序的ID的最大数量小于30。

有想法吗？

顺便说一下，我们将使用.NET的List<T>.Sort(Comparison<T>)在C#中进行排序，但底层算法显然与语言和平台无关。

---

如果您感兴趣，这里是此算法的实际需求：

我们的公司为每天访问大约20个位置的送货司机构建移动应用程序，这些位置是他们负责的100-150个总位置中的一部分。每天的位置列表是根据每个位置的库存动态分配的。库存较低的位置会获得新库存的交付，而仍具有足够库存的位置则不会被访问。

司机可以按任意顺序访问位置，但他们通常每天都会采取类似的路线（例如，在早晨交通较轻时访问城市南部的位置，然后在交通较重的时候访问城市北部的位置）。

我们选择不使用第三方路由软件，自动确定最有效的行驶路线。相反，我们发现让司机选择路线更好，因为路由软件很难应对像“那个建筑物的装卸区通常只在早上7点之前免费”或“需要签收交货单的人周五会提前离开”这样对交货时间表影响很大的限制条件。

无论如何，我们希望利用司机历史选择的方式，按照司机上次访问同一位置的顺序排序每天的行程安排。这将为司机每天提供一个漂亮的行程安排表，与他的偏好相匹配，而不需要他手动重新安排日程表，除非是非常特殊的情况。这将每天节省司机一两分钟的时间，随着时间的推移这些时间会逐渐累积。

每个历史行程实际上都是类似于（ID1，ID2，ID3，...，IDN，时间戳）的列表，但作为存储数百个过去的日程表的替代方法，我认为将每个N台历史行程分解为机器对可能更容易。这意味着我最多只需存储N*N-1个元组，因为新的排序总是会将较旧的排序映射出去。如果这是一个不好的简化，请告诉我。 ;-）

- Justin Grant

---

似乎有些模糊，B>A 是指 B 在 A 之前吗？ - Nahuel Fouilleul

那么明确一下，给定排序映射（C，A，1/1/1900），（C，B，1/1/2000）和要排序的列表（A，B，C，D），排序后的输出应该是（C，B，A，D）吗？ - flipchart

我认为多举几个例子并提供映射、输入和期望输出会很有用。 - flipchart

@NahuelFouilleul - 是的。我编辑了问题以澄清B>A的意思是“B在A之前”。 - Justin Grant

@flipchart - 是的，那将是预期的输出。我编辑了问题以包括您的示例，并在有时间时尝试添加更多内容。 - Justin Grant

Answer 1

你需要的是拓扑排序。使用这个搜索词你可以找到非常好的资源。

在你特定领域中有一个复杂的问题：循环（因为驱动程序随时间表现不一致）。你是对的，你需要打破依赖循环，否则拓扑排序将失败。

你还需要打破所有长度大于二的循环。

让我们把你的ID映射看作一个图：ID（地点）是节点。你的映射中的条目是边（从地点ID1到地点ID2）。做法就是这样简单。

while true
 allCycles = getListOfAllCycles();
 if (allCycles.length == 0) break;
 breakNode = chooseBreakNode(allCycles); //defined later
 deleteBreakNodeFrom(allCycles);

chooseBreakNode:
 chose the node which has been driven to the least //node is not important
 if ambiguous: chose the node in the dependency graph which is present in the highest number of cycles //breaks multiple cycles at once
 if ambiguous: chose the node which is in the longest cycle
 if ambiguous: pick an arbitrary node

也许我没有完全理解chooseBreakNode。这是一种启发式方法，可以根据您的需求进行调整。

- usr

Answer 2

我提出一种“替代”方法，但请告诉我是否误解了业务需求。

创建一个表格（DriverId、LocationId、Priority），用于存储每个司机位置的相对优先级。

每当您需要处理已完成的行程时，请从列表底部（最后访问的位置）开始，并为每个位置运行以下算法，向上移动列表：

• 如果该位置的优先级尚未高于其下方位置的优先级，则 newPriority = priorityBelow + 1。（如果下方没有任何内容，则 priorityBelow = 0）

处理完列表后，将优先级点重新归一化为1、2、3...（通过使最低优先级=1、第二低优先级=2等等）

然后，当您需要按照司机的相对优先值排序新行程时，只需按其相对优先级值对位置进行排序即可。

您考虑过这种方法吗？

---

编辑：根据下面的评论添加示例代码。

假设有4个历史行程：ABCD（最新），ACBE，CBDF，CBDFA（最旧），如何对一个新的行程ABCDEF进行排序？

static Dictionary<string, int> Priorities = new Dictionary<string, int>();

static void Main(string[] args)
{
    var itineraries = new string[][]{   
        new string[] { "C", "B", "D", "F", "A" },
        new string[] { "C", "B", "D", "F" },
        new string[] { "A", "C", "B", "E" },
        new string[] { "A", "B", "C", "D" } };

    //process past itineraries
    foreach (var itinerary in itineraries)
        ProcessItinerary(itinerary);

    //sort new itinerary
    string[] newItinerary = { "A", "B", "C", "D", "E", "F" };
    string[] sortedItinerary = newItinerary.OrderByDescending(
        x => Priorities.ContainsKey(x) ? Priorities[x] : 1).ToArray();

    Console.WriteLine(String.Concat(sortedItinerary));
    Console.ReadKey();
}

static void ProcessItinerary(string[] itinerary)
{
    itinerary.Reverse().Aggregate((below, above) =>
    {
        int priBelow = Priorities.ContainsKey(below) ?
            Priorities[below] : Priorities[below] = 1;

        if (!(Priorities.ContainsKey(above) &&
            Priorities[above] > priBelow))
            Priorities[above] = priBelow + 1;

        return above;
    });

    //normalize priorities
    // (note: running in reverse so that if priorities tie, 
    //  the older location has higher priority)
    int i = Priorities.Count;
    foreach (var pair in Priorities.OrderByDescending(x => x.Value))
        Priorities[pair.Key] = i--;
}

这将打印出：ABCDFE。

- Eren Ersönmez

---

我愿意尝试不同的方法，但我并不完全理解你提出的算法。你能给一个具体的例子来展示它是如何工作的吗？比如说：给定四个历史行程：ABCD（最新）、ACBE、CBDF、CBDFA（最旧），我该如何对一个新的行程ABCDEF进行排序呢？我故意添加了一些边缘情况——实际的日程变化不会这么多，但算法应该能够处理它们。 - Justin Grant

请查看添加的代码。请注意，这只是一个快速示例，以演示方法--没有数据库，也没有重构/优化。 - Eren Ersönmez