CODEWITHSUNDEEP
pythonarrayssortingmatrix
Brent Parker
Brent Parker

Reputation: 739

Python Sorting matrix rows into row-echelon...sort of

I'm trying to figure out how to write a custom sorting function for a two-dimensional array in Python 3.5. The idea is to turn an array into a semi-row-echelon form where any row with a leading 1 moves to the top of the other rows, anything with leading 0's to the bottom, and the rest sorted in between. You can see the example matrices below.

before = [
   [5, 3, 1, 2, 3, 1],
   [0, 1, -1, 2, -3, 4],
   [0, 0, 2, 2, -1, 3],
   [1, 2, 5, -2, 4, -3],
   [2, 1, 1, -1, 4, 2],
   [0, 0, 1, 4, 5, -1]
]

after = [
    [1, 2, 5, -2, 4, -3],
    [2, 1, 1, -1, 4, 2],
    [5, 3, 1, 2, 3, 1],
    [0, 1, -1, 2, -3, 4],
    [0, 0, 1, 4, 5, -1],
    [0, 0, 2, 2, -1, 3]
]

If I were doing this in Java, I would write a Comparator object or a compareTo method. But looking online, in Python 3+ it doesn't seem like the pythonic way to use cmp parameter when sorting anymore.

Right now I can use

for i in range(len(mat)-1, -1, -1):
    mat.sort(key=itemgetter(i), reverse=True)

to do this, but this doesn't move the rows whose first nonzero value is 1 to the top.

I'd appreciate any suggestions anyone might have to do this in the most pythonic way. Also, if anyone has any good resources on learning the proper pythonic way of doing other things, I'd appreciate that. I sometimes do things as though I'm writing them in other languages and don't realize that Python has a preferred way of doing it (I'm looking at you, list comprehensions).

Upvotes: 1

Views: 243

Answers (1)

eugenhu
eugenhu

Reputation: 1238

You could try something like:

mat.sort(key=lambda l: [
    (0, 0) if x == 1 else
    (2, 0) if x == 0 else
    (1, x)     for x in l
])

And take advantage of the fact that tuples and lists are compared lexicographically, first two elements are compared and so on.

Edit:

I change my opinion, I think doing it as shown above might be the better way compared to creating a comparison function (which isn't that much clearer), and quicker as well.

Test code:

TRIALS = 10000

mat = [
   [5, 3, 1, 2, 3, 1],
   [0, 1, -1, 2, -3, 4],
   [0, 0, 2, 2, -1, 3],
   [1, 2, 5, -2, 4, -3],
   [2, 1, 1, -1, 4, 2],
   [0, 0, 1, 4, 5, -1]
]

@functools.cmp_to_key
def matcmp(a, b):
    for ai, bi in zip(a, b):
        if (ai == bi): continue

        if (0 != ai != 1 and 0 != bi != 1):
            return a < b
        elif (ai == 1 or bi == 0):
            return -1
        else:
            return  1
    else:
        return 0

start = time.time()    

for i in range(TRIALS):
    sorted(mat, key=matcmp)

print(time.time() - start)

start = time.time()

for i in range(TRIALS):
    sorted(mat, key=lambda l: [
        (0, 0) if x == 1 else
        (2, 0) if x == 0 else
        (1, x)     for x in l
    ])

print(time.time() - start)

Output:

0.10232377052307129
0.09116077423095703

Upvotes: 1

Related Questions