How do I find the number of inversions in a matrix?-CodePudding

I have tried many different things and am very confused. The code below, when given a matrix usually finds the correct number of inversions but sometimes does not. However, it is always VERY close. I cannot tell what I am doing wrong.

Note: The number of inversions, in a matrix, is defined as the number of unordered pairs of cells {(i,j),(p,q)} such that M[i][j] > M [p][q] and i <= p and j <= q

#Matrix Input
matrix = []
side_len = int(input(''))
for x in range(0,side_len):
    matrix.append(input('').split(' '))

#Finding Matrix Inversions
inversions = 0
m_rows = side_len
m = range(0,m_rows)
for r in m:
    for c in m:
        for i in range(r,m_rows):
            for x in range(c,m_rows):
                if matrix[r][c] > matrix[i][x]:
                    inversions  = 1

print(inversions)

Note2: It takes inputs in the following form:

The first line contains the size of the matrix. Then lines 3-5 contain the matrix.

For this input it is correct (99 inversions):

10
430 988 763 573 19 76 580 640 844 602
249 754 265 955 424 586 584 522 734 608
720 124 92 840 213 592 874 342 707 484
397 137 823 512 61 842 587 992 833 782
594 82 536 858 388 311 795 971 184 880
578 903 355 21 742 568 612 615 909 670
98 657 158 273 168 218 114 106 210 298
888 803 379 423 12 118 733 159 440 917
390 17 819 745 389 561 312 1000 527 220
670 625 876 827 249 396 397 362 501 606

For this input it is incorrect (216 inversions, program finds 215):

6
177 931 790 323 962 608
617 304 35 633 588 310
225 403 213 900 694 184
496 837 314 673 56 488
757 596 607 585 688 286
420 217 568 561 539 529

CodePudding user response：

It seems I wasn't converting my strings to integers. I simply had to change this: matrix.append(input('').split(' ')) to this: matrix.append([int(i) for i in input('').split(' ')])

CodePudding user response：

You can use numpy:

from itertools import product
import numpy as np

np.random.seed(0)
a = np.random.randint(0, 5, (3, 3))
inversions = 0
for i, j in product(np.r_[:a.shape[0]], np.r_[:a.shape[1]]):
    inversions  = (a[:i 1,:j 1] > a[i,j]).sum() 
print(a)
print(f"{inversions=}")

It gives:

[[4 0 3]
 [3 3 1]
 [3 2 4]]

inversions=13