arrays - 在二维数组中查找所有可能的行式总和

Question

理想情况下，我正在寻找 c# 解决方案，但对算法的任何帮助都可以。

我有一个二维数组 (x,y)。最大列 (max x) 在 2 到 10 之间变化，但可以在实际填充数组之前确定。最大行数 (y) 固定为 5，但每列可以有不同数量的值，例如:

   1 2 3 4 5 6 7...10

A  1 1 7   9 1 1
B  2 2 5   2 2
C  3         3
D            4
E            5

为了寻找特定的总数，我需要得出所有可能的按行求和的总数。也就是说，按行总计可以是单元格 A1 + B2 + A3 + B5 + D6 + A7(每列一个值的任意组合)。

这个过程每次都会用不同的单元格值重复数百次，所以我正在寻找一个有点优雅的解决方案(比我能够带来的更好)。谢谢你的帮助。

Answer 1

问题大小

让我们首先考虑最坏的情况:

您有 10 列和每列 5(完整)行。应该清楚的是，您将能够获得(每个地方都有适当的人口数量)多达 5^10 ≅ 10^6 个不同的结果(解决方案空间)。

例如，以下矩阵将为您提供 3 列的最坏情况:

| 1  10  100 |
| 2  20  200 |
| 3  30  300 |
| 4  40  400 |
| 5  50  500 |

导致 5^3=125 个不同的结果。每个结果的形式为 {a1 a2 a3}，其中 ai ∈ {1,5}

很容易证明这样的矩阵对于任意数量的 n 列总是存在。

现在，要获得每个数值结果，您需要进行 n-1 次求和，加起来就是 O(n 5^n) 的问题大小。所以，这是最糟糕的情况，我认为对此无能为力，因为要知道有效执行求和所需的可能结果。

更多良性化身:

可以通过两种方式切断问题的复杂性:

较少的数字(即并非所有列都已满)

重复的结果(即几个部分和给出相同的结果，您可以将它们合并到一个线程中)。后面会讲到更多。

让我们看看后者的简化示例，其中包含两行:

| 7  6  100 |
| 3  4  200 |
| 1  2  200 |

乍一看，你需要做 2 3^3 和。但事实并非如此。当您将第一列相加时，您不会得到预期的 9 个不同的结果，而只有 6 个 ({13,11,9,7,5,3})。
因此，您不必将 9 个结果带到第三列，而只需将 6 个。

当然，这是以从列表中删除重复数字为代价的。 “删除重复的整数元素”was posted before in SO我不会在这里重复讨论，只是引用在列表大小 (m) 中执行合并排序 O(m log m) 将删除重复项。如果你想要更简单的东西，双循环 O(m^2) 就可以了。

无论如何，出于多种原因，我不会尝试以这种方式计算(平均)问题的大小。其中之一是排序合并中的“m”不是问题的大小，而是将任何两列相加后结果向量的大小，并且该操作重复(n-1)次......我真的不想做数学:(。
另一个原因是，当我实现算法时，我们将能够使用一些实验结果，并使我们免于我肯定会泄露的理论考虑。

算法

根据我们之前所说的，很明显我们应该针对良性情况进行优化，因为最坏的情况是丢失的情况。
为此，我们需要对列使用列表(或可变暗向量，或任何可以模拟它们的东西)，并在每列添加后进行合并。
合并可以被其他几种算法代替(例如在 BTree 上插入)而不修改结果。

所以算法(程序伪代码)是这样的:

 Set result_vector to Column 1
 For column i in (2 to n-1)
    Remove repeated integers in the result_vector
    Add every element of result_vector to every element of column i+1
           giving a new result vector
 Next column
 Remove repeated integers in the result_vector

或者按照您的要求，递归版本可能如下工作:

function genResVector(a:list, b:list): returns list  
                  local c:list  
                  {  
                   Set c = CartesianProduct (a x b)  
                   Set c = Sum up each element {a[i],b[j]} of c  </code>
                   Drop repeated elements of c
                   Return(c)
                  }

function ResursiveAdd(a:matrix, i integer): returns list
                  {
                   genResVector[Column i from a, RecursiveAdd[a, i-1]]; 
                  }
function ResursiveAdd(a:matrix, i==0 integer): returns list={0}

算法实现(递归)

我选择了一种函数式语言，我想翻译成任何程序语言都没什么大不了的。

我们的程序有两个功能:

genResVector，它对两个列表求和，给出所有可能的结果，删除重复元素，以及

recursiveAdd，它对矩阵列进行递归，将所有列相加。

recursiveAdd，它对矩阵列进行递归，将所有列相加。

代码是:

 genResVector[x__, y__] :=  (* Header: A function that takes two lists as input *)

      Union[        (* remove duplicates from resulting list *)

        Apply       (* distribute the following function on the lists *)

            [Plus,  (* "Add" is the function to be distributed *)

              Tuples[{x, y}],2] (*generate all combinations of the two lists *)];


 recursiveAdd[t_, i_] := genResVector[t[[i]], recursiveAdd[t, i - 1]]; 
                                       (* Recursive add function *)
 recursiveAdd[t_, 0] := {0};           (* With its stop pit      *)

测试

如果我们以您的示例列表为例

| 1 1 7 9 1 1 |  
| 2 2 5 2 2   |  
| 3       3   |  
|         4   |  
|         5   |  

并运行程序，结果为:

{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27}

最大值和最小值非常容易验证，因为它们对应于从每列中获取最小值或最大值。

一些有趣的结果

让我们考虑当矩阵每个位置上的数字有界时会发生什么。为此，我们将采用一个完整的 (10 x 5 ) 矩阵并用随机整数填充它。

在整数仅为 0 或 1 的极端情况下，我们可能会期待两件事:

一个非常小的结果集

执行速度快，因为中间会有很多重复的结果

如果我们增加随机整数的范围，我们可能会期望增加结果集和执行时间。

实验 1:用不同范围的随机整数填充的 5x10 矩阵





很明显，对于接近最大结果集大小 (5^10 ≅ 10^6 ) 的结果集，计算时间和“!= 结果数”具有渐近线。我们看到增加函数的事实只是表明我们离那个点还很远。

士气:你的元素越小，你就越有可能快速获得它。这是因为您可能会重复很多次!

请注意，对于测试的最坏情况，我们的 MAX 计算时间接近 20 秒

实验 2:非优化

有大量可用内存，我们可以通过蛮力计算，而不是去除重复的结果。

结果很有趣...... 10.6 秒! ... 等待!发生了什么 ？我们的“删除重复整数”小技巧消耗了很多时间，当没有很多结果要删除时，没有任何 yield ，但在试图摆脱重复时会失败。

但是当矩阵中的最大数远低于 5 10^5 时，我们可能会从优化中获得很多好处。请记住，我是在满载 5x10 矩阵的情况下进行这些测试的。

这个实验的精神是:重复整数去除算法很关键。

哼!

PS:如果我有时间编辑它们，我还有一些实验要发布。