How to efficiently (fast) calculate the transpose of a *permutation matrix* in Python3?

Question

The permutation matrix is represented as a list of positive integers, plus zero. The number indicates the position of the 1 in that row, e.g. a number zero would mean that the 1 is in the right-most position².

My first attempt is as follows, together with a printing function to help assess the result. It seems too convoluted to me. Please note that a permutation matrix multiplication is simpler than an ordinary matrix multiplication.

def transpose(m):
    """Transpose a permutation matrix.
    m: list of positive integers and zero."""
    c = {}
    idx = 0
    for row in reversed(m):
        c[-row] = idx
        idx += 1

    return list(map(
        itemgetter(1), sorted(c.items(), reverse=False, key=itemgetter(0))
    ))

def print_binmatrix(m):
    """Print a permutation matrix 7x7.
    m: list of positive integers and zero."""

    for row in m:
        print(format(2 ** row, '07b'), row)

# Usage example with a matrix 35x35. Ideally, it should scale up without sacrificing speed at smaller matrices like this.
transpose([8, 4, 21, 17, 30, 28, 1, 27, 5, 3, 16, 12, 11, 14, 20, 6, 33, 19, 22, 25, 31, 15, 13, 18, 10, 0, 7, 2, 9, 23, 24, 26, 29, 32, 34])
# Result
[25, 6, 27, 9, 1, 8, 15, 26, 0, 28, 24, 12, 11, 22, 13, 21, 10, 3, 23, 17, 14, 2, 18, 29, 30, 19, 31, 7, 5, 32, 4, 20, 33, 16, 34]

[2]: This way, the "zero matrix" is the one with 1's in the secondary diagonal, since only one 1 is allowed per column.

Answer 1

Perhaps only marginally, but the readability of your code can be improved by using enumerate and the reverse=True flag in sorted.

def transpose_r(ls): 
    return [len(ls)-1-k
            for k, Pk in sorted(enumerate(ls), 
                                reverse=True, 
                                key=itemgetter(1))]

If we index starting from the left, then this is further simplified.

def transpose_l(ls): 
    return [x for x, Px in sorted(enumerate(ls), key=itemgetter(1))]

---

The transpose has the funny property that transpose(ls)[ls[j]] == j. We can use this to build the transpose without sorting.

def transpose_l(ls):
    tr_ls = [0]*len(ls)

    for l in ls:
        tr_ls[ls[l]] = l

    return tr_ls

def transpose_r(ls):
    n = len(ls)
    tr_ls = [0]*n

    for l in ls:
        tr_ls[n - 1 - ls[l]] = n - 1 - l

    return tr_ls

Alternatively, we can use enumerate again.

def transpose_l(ls):
    tr_ls = [0]*len(ls)

    for ix, l in enumerate(ls):
        tr_ls[l] = ix

    return tr_ls

def transpose_r(ls):
    n = len(ls)
    tr_ls = [0]*n

    for ix, l in enumerate(ls):
        tr_ls[n - 1 - l] = n - 1 - ix

    return tr_ls