以优化的方式计算列表元素之间所有可能的差异

Question

我有一个一维列表的列表，例如 [[0], [1, 1], [4, 2, 4]....]。我想计算列表中所有列表的元素之间所有可能的差异。结果差异应该是这样的

差异 = [[0], [0, 0, 0, 0], [0, 2, 0, -2, 0, -2, 0, 2, 0],....]

我已经实现了一个包含三个嵌套 for 循环的暴力方法。第一个迭代所有列表，另外两个迭代特定列表以获取所有可能的差异。

我想知道是否有人可以想出一些聪明的算法并对其进行优化以使其运行得更快。谢谢！

Answer 1

正如评论中明确指出的，对于

O(n^2)

元素子列表，您不能低于

n

。但是，您可以提高一点效率，正如您建议的那样，只进行

n(n-1) / 2

减法。

以下是您想法的形式化：

获取大小为

L = [a,b,c]

 的子列表 

n = 3

考虑一个大小为

n X n

的矩阵 A 来存储差异。那么就清楚了

A = |a-a  a-b  a-c| = |   0      a-b   a-c|
    |b-a  b-b  b-c|   |-(a-b)     0    b-c|
    |c-a  c-b  c-c|   |-(a-c)  -(b-c)   0 |

您可以只计算具有

n(n-1) / 2

个条目的上三角形。对角线全为 0。下三角形值可以从上三角形值填充，因为

A

是斜对称的。

最后但并非最不重要的一点是，您以行优先顺序序列化

A

以获得所需的“差异列表”

D

。请注意，条目

a_{i,j}

将放置在

i*n + j

中的第

D

位置。 [我假设像 C 中一样基于 0 的索引。]