Calculate the all the possible difference between elements of a list in an optimized way

Question

I have a list of lists, for example [[0], [1, 1], [4, 2, 4], ...]. I want to iterate through each individual nested list and build a new list of lists that contains all the signed differences between values within each specific list. For this example list, the resulting list of lists would be:

differences = [[0], [0, 0, 0, 0], [0, 2, 0, -2, 0, -2, 0, 2, 0],....]

I have already implemented a brute-force method which contains three nested for loops. The first for loop iterates through all the lists and the other two for loops iterate over a specific list to get all the possible differences.

I was wondering if someone can come up with a more optimized algorithm that runs faster? Thanks!

Answer 1

As clearly pointed out in the comments, you cannot go below O(n^2) for a n element sublist. However, you can be a little bit efficient, as you suggested to only do n(n-1) / 2 subtractions.

Here's the formalization of your idea:

Take a sublist L = [a,b,c] of size n = 3

Consider a matrix A of size n X n to store the differences. Then clearly

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 |

You can just compute the upper triangle having n(n-1) / 2 entries. Diagonals are all 0's. The lower triangle values can be filled from the upper one, since A is skew-symmetric.

Last but not least, you serialize A in row-major order to get your desired 'difference list' D. Note that the entry a_{i,j} will be placed at the i*n + j-th place in D. [I have assumed 0 based indexing like in C.]