c# - 使用数组进行独特行程选择的最佳性能算法？

Question

如果给我三​​个等长的数组。每个数组代表我正在进行的公路旅行中到特定景点的距离(即第一个数组仅是主题公园，第二个仅是博物馆，第三个仅是海滩)。我不想确定所有可能的行程，每次行程都停在每种类型的景点之一，从不向后行驶，也从不两次访问同一个景点。

IE 如果我有以下三个数组:[29 50][61 37][37 70]

该函数将返回 3，因为可能的组合是:(29,61,70)(29,37,70)(50,61,70)

到目前为止我得到了什么:public int test(int[] A, int[] B, int[] C) {

    int firstStop = 0;
    int secondStop = 0;
    int thirdStop = 0;

    List<List<int>> possibleCombinations = new List<List<int>>();

    for(int i = 0; i < A.Length; i++)
    {
        firstStop = A[i];
        for(int j = 0; j < B.Length; j++)
        {
           if(firstStop < B[j])
           {
                secondStop = B[j];   
                for(int k = 0; k < C.Length; k++)
                {
                   if(secondStop < C[k])
                   {
                       thirdStop = C[k];
                       possibleCombinations.Add(new List<int>{firstStop, secondStop, thirdStop});
                   }
                }
           }
        }      
    }
    return possibleCombinations.Count();
}

这适用于以下测试用例:

示例测试:([29, 50], [61, 37], [37, 70])确定返回 3

示例测试:([5], [5], [5])确定返回 0

示例测试:([61, 62], [37, 38], [29, 30])失败返回 0

正确计算的正确算法是什么？性能最好的算法是什么？

我如何判断该算法的时间复杂度(即 O(N*log(N))？)

Answer 1

更新:这个问题已经用新的细节重写了，仍然是完全不清楚和自相矛盾的；尝试与原始发帖者澄清问题没有成功，并且原始发帖者承认在自己理解问题之前就开始编码。下面的解决方案对于最初陈述的问题是正确的；真正问题的解决方案是什么样的，没有人能说，因为没有人能说出真正的问题是什么。出于历史目的，我将把它留在这里。

---

让我们重述一下问题:

• 我们得到了三个数组，表示到道路沿线景点的距离。
• 我们希望枚举不回溯的景点的所有可能停靠点序列。 (注意:问题的陈述是枚举它们；给定的错误算法计算它们。这些是完全不同的问题。计算它们可以非常快。枚举它们是非常慢!如果问题是计算它们然后澄清问题。)
• 问题中没有给出其他约束。 (例如，问题中没有给出我们最多停在一个海滩，或者我们必须停在每一种海滩，或者我们必须在去博物馆之前去海滩。如果这些都是然后约束必须在问题中说明)

假设共有n个景点。对于每个景点，我们要么参观，要么不参观。似乎有 2ⁿ 种可能性。但是，有一个问题。假设我们有两个博物馆，M1 和 M2，都在这条路的 5 公里处。可能的路线是:

(Start, End)  -- visit no attractions on your road trip
(Start, M1, End) 
(Start, M2, End) 
(Start, M1, M2, End) 
(Start, M2, M1, End)

有五种非回溯可能性，而不是四种。

你想要的算法是:

• 按距离对景点进行分区，使所有分区包含距离相同的景点。
• 对于每个分区，生成该分区内所有子集的所有可能顺序的集合。。不要忘记“跳过所有这些”是一种可能的排序。
• 您想要的组合是所有分区排序集的笛卡尔积。

这应该会给你足够的提示来取得进展。这里有几个问题需要解决:分区，分区内的置换，然后取任意多个集合的叉积。 我和其他许多人都写过关于所有这些主题的文章，所以如果您不知道如何自己解决这些子问题，请做一些研究。

至于渐近性能:如上所述，给出的问题是枚举解决方案。如前所述，最好的情况是 2ⁿ在相同距离没有景点的地方，所以我们至少是指数级的。如果有碰撞，那么它就变成许多阶乘的乘积；我把它留给你解决，但它很大。

同样:如果问题是计算出数量 的解决方案，那就容易多了。您不必列举它们就知道有多少解决方案!只需计算出每个分区的排序数，然后将所有计数相乘即可。我将计算分区的渐近性能、计算排序数并将它们相乘作为练习。