合并两个列表之间缺乏比较的算法

Question

我正在寻找一种算法来合并两个排序列表，但是它们缺少一个列表的元素与另一个列表的元素之间的比较运算符。生成的合并列表可能不是唯一的，但任何满足每个列表的相对排序顺序的结果都可以。更准确地说:

给定:

• 列表 A = {a_1, ..., a_m} , B = {b_1, ..., b_n} . (它们也可以被视为集合)。
• 优先运算符 <在每个列表的元素之间定义，使得 a_i < a_{i+1} , 和 b_j < b_{j+1}对于 1 <= i <= m和 1 <= j <= n .
• A 和 B 的元素之间的优先运算符未定义: a_i < b_j没有为任何有效的 i 定义和 j .
• 相等运算符 =在 A 或 B 的所有元素中定义(它在 A 的元素和 B 的元素之间定义)。
• 列表 A 中没有两个元素是相等的，列表 B 也是如此。

生产:列表 C = {c_1, ..., c_r}这样:

• C = union(A, B) ; C 的元素是 A 和 B 的元素的并集。
• 如果c_p = a_i , c_q = a_j , 和 a_i < a_j , 然后 c_p < c_q . (元素的顺序应保留对应于集合 A 和 B 的 C 的子列表。
• 不存在i和 j这样 c_i = c_j .(删除 A 和 B 之间的所有重复元素)。

我希望这个问题是有道理的，而且我不是在问一些非常明显的问题，或者没有解决方案的东西。

上下文:

一个可构造的数字可以精确地表示为有理数域的有限多个二次扩展(使用高度等于域扩展数的二叉树)。因此，可构造数字的表示必须“知道”它所表示的字段。列表 A 和 B 表示有理数的连续二次扩展。A 和 B 的元素本身是可构造的数字，在上下文中定义以前较小的字段(因此优先运算符)。添加/乘以可构造的数字时，必须首先合并二次扩展域，以便二进制算术可以进行操作；结果列表 C 是二次扩展域，它可以表示字段 A 和 B 都可以表示的数字。(如果有人对如何以编程方式处理可构造数字有更好的想法，请告诉我。有关可构造数字的问题有 arisen before ，这里还有关于它们表示的一些 interesting responses。)

在有人问之前，不，这个问题不属于mathoverflow；他们讨厌算法(通常是非研究生水平的数学)问题。

实际上，列表 A 和 B 是链表(实际上以相反的顺序存储)。我还需要跟踪 C 的哪些元素对应于 A 和 B 中的哪些元素，但这是次要的细节。我求的算法不是mergesort中的merge操作，因为在合并的两个列表的元素之间没有定义优先运算符。一切最终都将在 C++ 中实现(我只希望运算符重载)。这不是家庭作业，最终将开源，FWIW。

Answer 1

我认为你不能比 O(N*M) 做得更好，尽管我很乐意犯错。

既然如此，我会这样做:

• 取 A 的第一个(剩余)元素。
• 在(剩下的)B 中寻找它。
  • 如果在B中没有找到，就把它移到输出
  • 如果您确实在 B 中找到了它，请将所有内容从 B 移动到并包括匹配项，并删除 A 中的副本。
• 重复上述直到A为空
• 将 B 中剩余的任何内容移至输出

如果您想检测 A 和 B 的不兼容顺序，则从步骤 2 中删除“(剩下的)”。搜索整个 B，如果您发现它“太早”，则引发错误。

问题是给定 A 的一般元素，没有办法在比线性时间(以 B 的大小)更好的时间内在 B 中寻找它，因为我们只有一个相等性测试。但显然我们需要以某种方式找到匹配项并且(这是我挥手的地方，我无法立即证明)因此我们必须检查 A 的每个元素是否包含在 B 中。我们可以避免一堆比较因为两组的顺序是一致的(至少我假设是一致的，如果不一致就无解)。

所以，在最坏的情况下，列表的交集是空的，并且 A 的所有元素都不能与 B 的 任何 元素进行顺序比较。这需要 N*M 等式测试才能建立，因此最坏情况下的界​​限。

对于您的示例问题 A = (1, 2, c, 4, 5, f), B = (a, b, c, d, e, f)，这给出了结果 (1,2,a, b,c,4,5,d,e,f)，这对我来说似乎不错。它在此过程中执行 24 次相等性测试(除非我数不清):6 + 6 + 3 + 3 + 3 + 3。以相反的方式与 A 和 B 合并将产生 (a,b,1,2,c ,d,e,4,5,f)，在这种情况下具有相同的比较次数，因为匹配元素恰好在两个列表中处于相同的索引处。

从例子中可以看出，操作不能重复。 merge(A,B) 导致列表的顺序与 merge(B,A) 的顺序不一致。因此 merge((merge(A,B),merge(B,A)) 是未定义的。一般来说，合并的输出是任意的，如果你使用任意订单作为新的完整订单的基础，你会生成相互不兼容的订单。