按递增顺序迭代一对数字

Question

我将在底部解释问题的来源，但这里是陈述。假设我有两个非负整数列表，它们分别是 (A[0] ... A[n]) 和 (B[0] ... B[m])。它们严格递增，因此对于所有的 i，A[i+1] > A[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)，先是降序指数，后跟它们各自的系数。为了有效地计算乘积，我真正想做的是将零次项收集在一起，然后是一次项等。当前的代码通过进行半心半意的尝试以获得效率，然后执行一种通用的多项式加法来处理不期望的系数顺序。我觉得我们应该能做得更好！

- Rupert Swarbrick

---

你使用的是哪种编程语言？数组有多大？ - Bohemian

波西米亚：请阅读第二段。如果您试图回答问题，也请阅读其他段落。 - Rupert Swarbrick

如下有几个人指出，当我说“在每个列表上迭代一次”时，我很傻。我会进行编辑，以便该语句在上面更加合理。 - Rupert Swarbrick

数组有多少空余？例如？因为如果多项式中存在大的空洞（如x^500+3*x^120+x），我们要么最好采用分而治之（跳过空洞），要么像手动计算一样处理乘法。 - GameAlchemist

附注: 等效的Python表达式: sorted([(a,b) for a in A for b in B], key=sum) - Robᵩ

Answer 1

这个问题与计算几何学家多年来的主要烦恼——排序X + Y——只有表面上的区别。 （请参见Joseph O'Rourke的（开放的）问题41。）为了对实施者进行总结，当指数仅能够相加和比较时，已知的最快算法是O（m n log（m n）），这也是显而易见的。如果指数是有界整数，则适用Peter的傅里叶方法。许多聪明的人已经思考了这个问题很长时间，因此我不希望很快出现更好的算法。

- David Eisenstat

---

这是一个很棒的答案，谢谢！我本来希望得到一个“是的，很容易，只需要这样做...”的回答，但“不，很难，原因是...”也很酷。我要去读一些论文了。 - Rupert Swarbrick

哎呀，我突然意识到我还没有正式接受这个答案。对此感到抱歉。 - Rupert Swarbrick

Answer 2

我想知道您的多项式有多稀疏？

对于密集多项式的乘法，一个值得考虑的选择是计算多项式的傅里叶变换，然后将它们的傅里叶系数相乘。

这样可以在O（nlogn）的时间复杂度内完成多项式乘法，其中n是多项式的次数。

对于像（1+x^1000000）*（1+x^1000000）这样的稀疏多项式，n大约为1000000，而当前的算法只需要很少的几个周期。

关于这种傅立叶方法的好说明可以在这些讲座笔记中找到。

- Peter de Rivaz

---

我认为我希望成本随项数而扩展，而不是随度数扩展，因此应该假设多项式非常稀疏。虽然我不知道这种傅里叶方法，但它很迷人！ - Rupert Swarbrick

傅里叶方法需要浮点数和舍入。这可能不适用于计算机代数系统。 - Alexandre C.

Answer 3

据我所知，由于以下原因，即使您希望针对复杂度为O(N*M)的解决方案，也不太可能得到解决。

假设数组为(a1, a2, a3, a4)和(b1, b2, b3, b4, b5)，

可能的配对如下：

a1b1 a1b2 a1b3 a1b4 a1b5
     a2b1 a2b2 a2b3 a2b4 a2b5
          a3b1 a3b2 a3b3 a3b4 a3b5
               a4b1 a4b2 a4b3 a4b4 a4b5

现在对于每一行，左边的一对总是要在右边的一对之前被挑选出来。

1. 所以第一个候选者是 a1b1。
2. 然后一旦选择了 a1b1，下一个候选者就是 a1b2 和 a2b1。
3. 假设选择了 a1b2。那么下一个候选者就是 a1b3 和 a2b1。
4. 现在假设选择了 a2b1。那么下一个候选者就是 a1b3、a2b2 和 a3b1。

因此我们可以看到，随着向前移动，该位置的候选人数呈线性增长。

因此，在最坏的情况下，你将需要进行大约 N*M*M 次比较。

一种 O(N*Mlog(M*N)) 的方法。(其中N = a.size()，M = b.size())

for ( int i = 0; i < a.size(); i++ )
  for ( int j = 0; j < b.size(); j++ )
    sumVector.push_back( a[i] + b[j] );

sort( sumVector ); // using merge sort or quicksort.

- Abhishek Bansal

---

好的，是的，我想是这样的。但那也适用于完全未排序的输入。我们肯定可以做得更好吧？！ - Rupert Swarbrick

为什么不这样做呢：

1. 有m个排序向量：AiBj（i是向量的索引）（j=0 ... m）[O(n*m)]
2. 然后递归地合并每两个向量以生成一个排序向量。 每个向量合并可以需要[O(m*n)]，因为这是结果向量的长度 然后添加前缀O(log(m))，即此类合并的数量。

总而言之，我们得到O(log(m)(mn))。我一定是错了，因为n和m应该是对称的，但我不确定我的错误在哪里。 - lkanab

为什么是 logm？应该是 m，因为你正在合并 m 个向量。 - Abhishek Bansal

看我的答案。因为你已经排序了输入，所以实际上每个生成的列表成员只需要进行一次比较就可以了。把它想象成一个冒泡排序，你总是试图将一个数字插入到当前计算出的最高数字下面。 - Dylan Brams

Answer 4

我希望只存储一个恒定的状态，并且只对每个列表进行一次迭代就能实现。

我认为这是不可能的。我无法提供严谨的数学证明，但请考虑以下问题：您的问题有两个部分：

1）从A和B生成所有的配对。 2）确保它们按照递增总和的顺序排列。

让我们放弃第二部分以使其更容易实现。最简单的实现方法是：

foreach a in A:
  foreach b in B:
    emit (a, b)

我希望您能同意这种做法是最有效的方法。但是我们已经在B的长度上迭代了A次。

因此，这样做的时间复杂度至少为O(A*B)，但是您需要O(A+B)的时间复杂度。

- Sebastian Redl

---

原帖作者自己说：“我想收集所有的n * m”。然后他要求O(n+m)，这显然是不可能的。 - fjardon

是的，你说得对。我的意思是我想避免来回移动，但显然我没有仔细考虑我的意思。状态部分的恒定量是有道理的。我想我的意思是我希望算法的复杂度约为n*m（但不是n^2 * m）。 - Rupert Swarbrick

Answer 5

那么让我们来看两个“稀疏数组”sA和sB，它们只包含如原帖中所述的非空度数/系数数字。
例如：

A   =  x^5 + 3*x^2 + 4
sA  = [ 5, 1, 2, 3, 0, 4 ]

B = 2*x^6 + 5*x^3 + 8*x
sB = [ 6, 2, 3, 5, 1, 8]

我建议的是按照手动操作的方式进行操作，因此它们需要m * n的时间，其中m和n是非空系数的数量，而不是A和B的度数p和q的乘积。
由于您说m和n很小，所以m*n不是什么大问题。
在计算时存储系数，可以使用稀疏数组（可能会昂贵）或哈希表。索引或键是度数，而值是相应的系数。
这里是javascript的实现示例，使用哈希表：

http://jsbin.com/ITIgokiJ/2/edit?js,console

一个例子：

A     =   "x^5+3x^2+4"
B     =   "2x^6+5x^3+8x^1"
A * B =   "2x^11+11x^8+16x^6+15x^5+44x^3+32x^1"

这段代码：

function productEncodedPolynoms( sA, sB) {
   var aIndex = 0 ;
   var bIndex = 0 ;
   var resIndex = 0 ;
   var resHash = {} ;
   // for loop within sA, moving 2 items at a time
   for (aIndex = 0; aIndex < sA.length ; aIndex+=2) {
       // for loop within sB, moving 2 items at a time
       for (bIndex = 0; bIndex < sB.length ; bIndex+=2 ) {
           resIndex = sA[aIndex]+sB[bIndex] ;
           // create key/value pair if none created
           if (resHash[resIndex]===undefined)  resHash[resIndex]=0;
           // add this product to right coefficient
           resHash[resIndex] += sA[aIndex+1]*sB[bIndex+1];
       }
   } 
   // now unpack the hash into an encoded sparse array
   // get hash keys
   var coeff = Object.keys(resHash);
   // sort keys in reverse order
   coeff.sort(reverseSort);
   encodedResult = [];
   for (var i=0; i<coeff.length; i++ ) {
     if (resHash[coeff[i]]) {
       encodedResult.push(+coeff[i]);          // (+ converts to int)
       encodedResult.push(+resHash[coeff[i]]);
     }
   }
   return encodedResult;
}

例子：

sA = [ 5, 1, 2, 3, 0, 4 ] ;

sB = [ 6, 2, 3, 5, 1, 8] ;

sAB = productEncodedPolynoms ( sA, sB );

打印结果的实用工具：

function printEncodedArray(sA) {
  res='';
  for (var i=0; i<sA.length; i+=2) {
    if (sA[i+1]) {
        if (sA[i+1] != 1 || sA[i]==0) res+=sA[i+1];
        if (sA[i]!=0) res+='x^'+sA[i];
        if (i!=sA.length-2) res+='+';
    }
  }
  return res;
}

// utilities
function reverseSort(a,b) { return b-a ; }

- GameAlchemist

Answer 6

使用算法在排序数组中找到一对数使它们的和等于指定常数K很简单，详见这个问题。

总结

最终解决方案的时间复杂度为O((M+N)*(M+N))，最多比下限的M*N差4倍（只输出所有的对）。因此，常数因子只有4。

编辑：糟糕，它并不是我想象中的O((M+N)*(M+N))，显然，它是O(K*(M+N))，其中K是两个数组中最高的和。我不确定这个算法能否得到改进，但似乎该解决方案与Peter de Rivaz所描述的快速傅里叶变换方法类似。

排序数组求和算法

在该算法中，我们将较低指针设置为0，将较高指针设置为数组结尾。如果这两个位置上的和大于K，则减小较高指针。如果它小于，则增加较低指针。这是因为在任何迭代中，arr[low]是目前为止可以推导出答案的最低元素。同样，arr[high]是最高的。因此，如果我们取最低和最高的元素，且它们的和大于K，那么我们知道与arr[high]配对的任何其他组合都会大于K。因此，arr[high]不能是任何解的一部分。因此，我们可以将其从数组中删除（通过减小high指针实现）。

将其应用于您的问题

将此应用于您的问题，思路是，我们遍历可能的和，也就是从0到A[len(A)-1]+B[len(B)-1]。对于每个可能的和，我们运行上述算法。对于您的问题，我们将较低指针设置为数组A，将较高指针设置为数组B。

对于原始算法，只要找到一个和等于常数的对，就会停止执行。对于您的问题，您将每次将ptr_A增加1并将ptr_B减少1。这有效，因为您的数组严格递增。因此，如果我们发现A[ptr_A]+B[ptr_B]==K，那么对于所有low_B<ptr_B和high_A>ptr_A，都有A[ptr_A]+B[low_B]<K和A[high_A]+B[ptr_B]>K。

这将找到所有的配对，因为对于每个可能的和K，它将找到所有相加得到K的配对，并且我们遍历所有可能的和K。

额外地，这个算法将会基于列表A中递增的值排序输出（你可以通过交换指针来基于列表B中递增的值进行排序），而且我们不需要随机访问数组。

Python 代码

Python 实现:

def pair_sum(A,B):
    result = []
    max_sum = A[-1]+B[-1]
    for cur_sum in range(max_sum+1): # Iterate over all possible sum
        ptr_A = 0        # Lower pointer
        ptr_B = len(B)-1 # Higher pointer
        while True:
            if A[ptr_A]+B[ptr_B]>cur_sum:
                ptr_B -= 1
            elif A[ptr_A]+B[ptr_B]<cur_sum:
                ptr_A += 1
            else:
                result.append((A[ptr_A],B[ptr_B]))
                ptr_A += 1
                ptr_B -= 1
            if ptr_A==len(A):
                break
            if ptr_B==-1:
                break
    return result

def main():
    print pair_sum([0,1,2],[1,4])
    print pair_sum([0,1],[0,1])
    print pair_sum([0,1,3],[1,2])

if __name__=='__main__':
    main()

将打印：

[(0, 1)，（1，1），（2，1），（0，4），（1，4），（2，4）]
[(0, 0），（0，1），（1，0），（1，1）]
[(0, 1)，（0，2），（1，1），（1，2），（3，1），（3，2）]

按要求输出。

- justhalf

---

这很不错，但我不想假设指数的密度。不过还是感谢仔细的撰写！ - Rupert Swarbrick

Answer 7

为什么不先生成未排序的二维数组，然后对其使用快速排序呢？

ED：看起来如果你在初始迭代和数组生成过程中使用比较算法来略微智能地生成最终数组，那么你稍后可以使用更具体的排序算法（例如平滑排序），并且性能接近O（2（m * n）），最坏情况下为O（m * n +（m * n）log（m * n））

ED2：我绝对确定你可以编写一个O（m * n）的算法。你要做的就是干净地生成数组。 我没有时间写伪代码，但是如果你 1.为每个数组设置最小迭代器、最大迭代器和当前迭代器，以及它们的当前最大总和。 2.生成第一对 3.迭代一个变量，将其与另一种可能的第三对进行比较（将其保存在临时变量中），然后将其保存到输出中或将其他数组保存到输出中并重新开始。

我将其视为两行带有三种颜色的块：红色表示完全完成，蓝色表示“至今最高”和未完成。您一次只处理一个块行，为结果数组生成下一个值，始终比较当前侧基线的组合是否低于当前处理的总和。每次总和较低时，您将新的最低结果设置为刚刚计算的结果，将先前的最低结果添加到已排序的输出数组中，并使用以前的低值（及其行）作为基线开始累加。永远不要回到红色块中，并在找到新的相反侧低点时每次切换哪一侧是蓝色。

您不应该计算两个结果，而应该得到一个排序的数组。

它本质上是一种浮动顶部冒泡排序。您知道计算出的值高于当前总和，直到不再高于当前总和为止，您会处理数组中较低的寄存器。当它不再更高时，您将顶部值向上切换并返回到迭代当前较小成员的数组的点。例如：

A：（1 5 10）

B：（1 6 9）

（1,1） ->（1,6）高于（1,5），因此添加（1,5）使（1,6）最高

（5,6）高于（1,6），因此添加（1,6）使（5,6）最高，移至（1,9）

（1,9）小于（5,6），因此[添加（1,9）并增加A上的已完成]

当前数组：（1,1），（1,5），（1,6），（1,9）

(1, 10) 相当于 (5,6) 所以两者相加，在B上增加完成，从（5,9）开始

（5,9）比（10,1）高，因此添加（10,1）使（5,9）最高移动到（10,6）

（10,6）比（5,9）高，所以......

无论如何，如果您设置得当，则每次添加到最终数组只进行一次比较，并且可以在不分支的情况下即时构建它。如果您不需要将最终数组保存在任何内存中，则FFT可能会更快，但这应该可行。

- Dylan Brams