以递增的顺序迭代成对的数字

我将在底部解释问题的来源,但这是声明.假设我有两个非负整数列表,我将编写(A[0] ... A[n])和(B[0] ... B[m]).他们是严格递增的,所以A[i+1] > A[i]所有的i也是类似的B.我想n * m按照它们总和的递增顺序收集所有元素对.

所以,例如,如果A = (0 1 2)和B = (1 4),那么我想最终收集((0 1) (1 1) (2 1) (0 4) (1 4) (2 4)).如果有一个平局,我不关心我收集这两个元素的顺序.例如,如果A = (0 1)和B = (0 1),那么我不介意哪个混合术语,(0 1)或者(1 0),我先拿起.

显然,我希望这是合理有效的.我希望它有可能及时渐近m * n.具体来说,如果我对输入一无所知,我希望有序输入能使这个问题比同等问题更容易.当我第一次提出问题时,我在思考的是我们必须存储的状态量.我希望这可能是一个恒定的数额,但也许这是不现实的.(自那以后我尝试过的都失败了!)

代码实际上是用Lisp编写的,但我认为问题陈述几乎与它无关.输入最自然地会作为单链接列表,但无论如何我都必须提前撤消它们,所以如果随机访问是相关的,我可以将它们作为数组.如果它是相关的,我希望这主要是在非常小的列表上调用,因此运行时的大量常量项/常数因子可能会排除解决方案.(虽然我很想知道算法的想法!)

背景:我一直在查看Maxima的源代​​码,这是一个计算机代数系统,特别是它的代码,用于两个多项式的乘法.多项式以"稀疏格式"表示,因此x^5 + x^2 + 2可能显示为(5 1 2 1 0 2),下降指数后跟各自的系数.为了有效地计算产品,我真正想做的是收集零度项,然后是1度项等等.当前的代码通过对其进行半心半意的刺激以提高效率来避免解决这个问题,然后做一个一类通用多项式加法,以按照它不期望的顺序处理系数.我觉得我们应该做得更好!