Vic*_*Liu 9 language-agnostic algorithm
我正在寻找合并两个排序列表的算法,但它们缺少一个列表的元素和另一个列表的元素之间的比较运算符.生成的合并列表可能不是唯一的,但是满足每个列表的相对排序顺序的任何结果都可以.更确切地说:
鉴于:
{a_1, ..., a_m},和B = {b_1, ..., b_n}.(它们也可以被视为集合).<在每个列表的元素之间定义
的优先级运算符a_i < a_{i+1},以及b_j < b_{j+1}for 1 <= i <= m和for 1 <= j <= n.a_i < b_j未定义任何有效i和j.=在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都可以表示的数字.(如果有人更好地了解如何以编程方式处理可构造数字,请告诉我.之前出现了关于可构造数字的问题,这里还有一些关于他们代表性的有趣回答.)
在有人问之前,不,这个问题不属于mathoverflow; 他们讨厌算法(通常是非研究生水平的数学)问题.
实际上,列表A和B是链表(实际上以相反的顺序存储).我还需要跟踪C中哪些元素与A和B中哪些元素相对应,但这是一个小细节.我寻求的算法不是mergesort中的合并操作,因为在合并的两个列表的元素之间没有定义优先级运算符.一切都将最终用C++实现(我只想让运算符重载).这不是家庭作业,最终将是开源的,FWIW.
我认为你不能比 O(N*M) 做得更好，尽管我很乐意犯错。
既然如此，我会这样做：
如果您想检测 A 和 B 的不兼容顺序，请从步骤 2 中删除“(what's left of)”。搜索整个 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)) 是未定义的。一般来说，合并的输出是任意的，如果您使用任意订单作为新的完整订单的基础，您将生成相互不兼容的订单。