这个模式有什么优雅的解决方案？多级搜索

Question

假设我们有多个整数数组。您可以将每个数组视为一个级别。我们尝试找到一系列元素，每个数组恰好一个元素，并以相同的谓词进入下一个数组。例如，我们有v1、v2、v3作为数组:

v1  | v2  | v3
-----------------
1   | 4   | 16
2   | 5   | 81
3   | 16  | 100
4   | 64  | 121

我可以说谓词是：next_element == previous_element^2
上面例子中的一个有效序列是：2 -> 4 -> 16
实际上，在这个例子中没有另一个有效的序列。 我可以编写三个循环来暴力解决上述示例，但如果数组数量是可变的，但顺序已知当然，您会如何解决此问题？

非常感谢任何提示或设计模式的参考。我将用C++实现它，但只需要思路。

谢谢，

- Khaled Alshaya

---

你需要的是算法，而不是模式。这将是解决问题的方案。 - ima

这里有一个问题：似乎你的谓词可以任意复杂，因此可以同时处理1到N个数组...很难想出一个能够处理整个问题的解决方案。 - Matthieu M.

此外，是否存在重复的可能性，如果有，您如何处理它们（您希望每个重复项都有一个解决方案，还是只希望整体上只有一个解决方案？） - Matthieu M.

Answer 1

如果您预先对数组进行排序，搜索速度将会更快。您可以从较小的数组开始，在每个数组中二分查找期望的数字。这将是O(nklogM)的时间复杂度，其中n是最小数组的大小，k是数组数量，M是较大数组的大小。

如果使用哈希映射而不是数组，则可以更快地进行搜索。这将让您在O(n*k)的时间复杂度内进行搜索。

如果使用反向函数（搜索早期的数组）不是一个选项，那么您应该从第一个数组开始，n = 第一个数组的大小。

为简单起见，我将从第一个数组开始。

//note the 1-based arrays
for (i : 1 until allArrays[1].size()) {
  baseNumber = allArrays[1][i];
  for (j: 2 until allArrays.size()) {
    expectedNumber = function(baseNumber);
    if (!find(expectedNumber, allArrays[j]))
        break;
    baseNumber = expectedNumber;
  }
}

你可以添加一些null检查和布尔值，以知道序列是否存在

- Samuel Carrijo

---

我在我的问题中举了一个谓词的例子。对于我正在使用的谓词，元素实际上并没有被排序，而且我认为它们不能被排序。我试图想出的方法是，如果数组的数量是可变的，找到元素序列的方法。 - Khaled Alshaya

Answer 2

设计模式适用于类和API设计，以提高代码质量，但它们并不用于解决计算问题。

根据情况：

1. 如果数组是随机排序的，并且您有有限的空间要求，则暴力破解是唯一的解决方案。时间复杂度为O(N^k)（其中k = 3），空间复杂度为O(1)。
2. 如果谓词不可逆（例如，SHA1(next_elem) xor SHA1(prev_elem) == 0x1234），则暴力破解也是唯一的解决方案。
3. 如果您可以花费空间，则为v2和v3创建哈希集，这样您就可以快速找到满足谓词的下一个元素。时间复杂度为O(N + b^k)，空间复杂度为O(kN)（其中b = 在给定prev_elem的情况下满足谓词的next_elem的最大数量）。
4. 如果数组已排序且有界，则还可以使用二进制搜索而不是哈希表来避免使用空间。时间复杂度为O(N (log N)^k-1 + b^k)，空间复杂度为O(1)。

（所有空间计数都不考虑由递归引起的堆栈使用。）

一种最多消耗O(Nb^k)空间的通用方法是通过连续过滤来构建解决方案，例如：

solutions = [[1], [2], ... [N]]

filterSolution (Predicate, curSols, nextElems) {
   nextSols = []
   for each curSol in curSols:
      find elem in nextElems that satisfy the Predicate
      append elem into a copy of curSol, then push into nextSols
   return nextSols
}

for each levels:
  solutions = filterSolution(Predicate, solutions, all elems in this level)
return solutions

- kennytm

---

我喜欢这个流水线的想法！ - Matthieu M.

Answer 3

你可以生成一个单独的索引，将一个数组的索引映射到另一个数组的索引。通过索引，您可以快速查看是否存在解决方案。

生成索引需要采用蛮力方法，但只需执行一次即可。如果要改进数组搜索，请考虑使用更适合快速搜索的数据结构（例如红黑树，而不是数组）。

- Cthutu

---

之前的帖子建议使用排序数组和二分查找 - 这比红黑树要快得多。如果您需要将许多项插入到数组中间，我会考虑使用列表而不是数组。这确实是内存使用和速度之间的权衡。 - Cthutu

Answer 4

我会将所有向量都保持为 堆，这样当搜索元素时，可以获得 O(log n) 的复杂度。因此对于总共 k 个向量，你可以得到类似于 O(k * log n) 的复杂度。

- Dr.Optix

Answer 5

如果谓词保留数组中的排序（例如，对于您的示例，如果保证所有值都是非负数），则可以调整合并算法。将每个数组的关键字视为结束值（在应用谓词所需的所有数组的次数后获得的值）。

如果谓词不保留排序（或者数组没有排序），则可以首先按结束值进行排序，但需要这样做表明另一种方法可能更好（例如其他地方建议的哈希表）。

基本上，检查下一个结束值是否对所有数组都相等。如果不是，则跨越最低值（仅在一个数组中）并重复。如果您得到所有三个相等，则这是一个（可能的）解决方案-在搜索下一个之前跨越所有三个。

“可能”的解决方案，因为您可能需要进行检查-如果谓词函数可以将多个输入值映射到相同的输出值，则可能存在某些数组中找到的值（但不是第一个或最后一个）错误的情况。

编辑-当谓词不将每个输入映射到唯一输出时，可能会出现更大的问题-此时无法思考。基本上，合并方法可以很好地工作，但仅适用于某些类型的谓词函数。

- user180247