在矩阵中有效地搜索四倍

Question

我有一个不同数字的矩阵，我需要一种有效的算法来查找所有四元组(四个条目，每个条目两个在同一行，每个条目在同一列)，其中所有四个数字都是正数。例如：

• 1 2 0 0
• 1 1 0 0
0
• 0 1 1

在这里，我们有一个这样的四倍

• 1 2
1
• 1

很容易找到一个低效的解决方案，但我需要一些高效的东西。对于任何想法，我将不胜感激！

Answer 1

如果这些是非稀疏矩阵，我认为你能做的最好的事情就是取行对的按位乘积，其中你使用每个元素的"真实性"。 我会稍微改变一下你的例子：

1 2 0 1
1 1 0 0 
0 1 1 1

这三款产品将是

1*2 T T F F
1*3 T F T F
2*3 F T F F

如果你有一个 N*M 矩阵，其中 M 在硬件矩阵指令的线性处理能力范围内，那么这是一个快速的 N^2 算法。

现在，任何具有至少两个T值的结果都表示四边形;您可以在 K^2 时间内生成所有坐标，其中 K 是行中Ts 的数量。

不幸的是，密集数组会给出令人讨厌的 N^2 M^2 结果。 但是，它是可处理的，可维护的，我认为它适用于半稀疏应用程序。