2

If I have a symmetrical matrix of size n x n, say:

A = [ 0 3 5 0 4
      3 0 1 2 0
      5 1 0 0 6
      0 2 0 0 2
      4 0 6 2 0 ]

(representing the weights of edges between vertex i and vertex j in an adjacency matrix, but that is beside the point)

The easiest way to iterate over this matrix is to use a nested loop:

for i in range(n):
    for j in range(n):
        value = A[i][j]

However, this means that i am "doubling up" on the symmetrical parts of the matrix ie. (i,j) = (j,i). To avoid this I can change the nested loop to:

for i in range(n):
    for j in range(i+1, n):
        value = A[i][j]

Which only iterates over the top triangular part of the matrix (ignoring i = j because it is always 0)

My question is: What is the 4 dimensional equivalent of this?

If I want to compare every element in A with every other element in A, this is the equivalent of placing a copy of matrix A perpendicular to the edge of the original A matrix and iterating over the "cube" generated.

I can do this with:

for i in range(n):
    for j in range(i+1, n):
        value1 = A[i][j]
        for k in range(n):
            for l in range(k+1, n):
                value2 = A[k][l]
                foo(value1, value2)

My problem is that this does not take into account that:

foo(A[3][5], A[2][4]) is exactly the same as foo(A[2][4], A[3][5])

Is there a way that I can structure my loops such that the symmetries of the 4 dimensional matrix can be exploited in the way that those of the 2 dimensional one were in my second example?

Please ignore the fact that I am using 'pythonic' pseudocode for my examples, I am not after a python specific answer - more just an understanding of how the loop structure would work; so I can implement it in any language..

Gus Kenny
  • 639
  • So what you want to do is to iterate through all elements above the the main diagonal two-by-two without repeating any set of pairs? – Matheus208 Oct 22 '15 at 13:24
  • Pretty much. I am having trouble visualising it in 3 (or maybe 4?) dimensions. But yes. Iterate over all pairs from two identical, symmetrical 2D matrices, without repeating any pairs.. – Gus Kenny Oct 22 '15 at 14:07
  • Do you want to include or exclude foo(A[2][4], A[2][4])? – Jeppe Stig Nielsen Mar 10 '16 at 00:22
  • exclude, i suppose, as they will be the same value and the function operating on them will be a comparative function – Gus Kenny Mar 10 '16 at 01:11

1 Answers1

1

With your initial code, you check each 'checkmark':

\begin{array} {c|ccccc} i/j&1&2&3&4&5\\ \hline 1&.&\checkmark&\checkmark&\checkmark&\checkmark\\ 2&.&.&\checkmark&\checkmark&\checkmark\\ 3&.&.&.&\checkmark&\checkmark\\ 4&.&.&.&.&\checkmark\\ 5&.&.&.&.&.&\\ \end{array}

With the second array, you will need to check each $(i,j)_{A_1}$ against each $(i,j)_{A_2}$, but only if $i_1\le i_2$ AND $j_1\le j_2$, excepting if both $i_1=i_2$ and $j_1=j_2$.

This motivation is because although we have defined equality in matrix $A_1$ and $A_2$, we have not defined equality between an element of $A_1$ and an element of $A_2$, which can be defined as $(i_1=i_2) \land (j_1=j_2)$.

So for example, if from matrix $A_1$ we are considering $(1,2)$, we check:

\begin{array} {c|ccccc} i/j&1&2&3&4&5\\ \hline 1&.&\color{red}\checkmark&\checkmark&\checkmark&\checkmark\\ 2&.&.&\checkmark&\checkmark&\checkmark\\ 3&.&.&.&\checkmark&\checkmark\\ 4&.&.&.&.&\checkmark\\ 5&.&.&.&.&.&\\ \end{array}

and if we are considering $(2,4)$, we check:

\begin{array} {c|ccccc} i/j&1&2&3&4&5\\ \hline 1&.&.&.&.&.\\ 2&.&.&.&\color{red}\checkmark&\checkmark\\ 3&.&.&.&\checkmark&\checkmark\\ 4&.&.&.&.&\checkmark\\ 5&.&.&.&.&.&\\ \end{array}

So your code should look more like:

for i in range(n):
    for j in range(i+1, n): [
        for k in range(i,n):
            for l in range(j, n): [
                if [i!=k && j!=l]: [
                    value1 = A[i][j]
                    value2 = A[k][l]
                    foo(value1, value2)
                                   ]
                                  ]
                           ]
JMP
  • 21,771