3
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ What are you trying to optimize, speed or memory usage? \$\endgroup\$ – pacmaninbw Apr 30 '20 at 18:28
  • \$\begingroup\$ Can you clarify how you are encoding a "permutation matrix" as a list of natural numbers? Do the list values represent the zero-based index of the "1" in each row of the permutation matrix? \$\endgroup\$ – Nick2253 Apr 30 '20 at 18:29
  • \$\begingroup\$ And when you say efficiently - does that include pulling in libraries (numpy) to do this properly? \$\endgroup\$ – Reinderien Apr 30 '20 at 18:42
  • \$\begingroup\$ Also, can you include code in your question that calls your functions with realistic data? \$\endgroup\$ – Reinderien Apr 30 '20 at 18:43
  • \$\begingroup\$ @pacmaninbw speed \$\endgroup\$ – olyk Apr 30 '20 at 18:45
3
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ Your third option is 3 times faster. Thanks! \$\endgroup\$ – olyk Apr 30 '20 at 21:53
  • \$\begingroup\$ However the result doesn't seem to match. \$\endgroup\$ – olyk Apr 30 '20 at 22:05
  • \$\begingroup\$ @viyps The transpose_l functions assume indexing from the left! I've added the _r versions. \$\endgroup\$ – Andrew Apr 30 '20 at 22:16
  • 1
    \$\begingroup\$ Ok! The R version is also faster. I have another problem which is to convert a number to such matrices, it has much more room for optimization, but it is far more involved to explain. If you are interested I can post another question. \$\endgroup\$ – olyk Apr 30 '20 at 22:35
  • 1
    \$\begingroup\$ @viyps Sure, go ahead. If not I, someone else will surely give you some tips! \$\endgroup\$ – Andrew Apr 30 '20 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.