Matrix data structure

Question

A simple 2 dimensional array allows swapping rows (or columns) in a matrix in O(1) time. Is there an efficient data structure that would allow swapping both rows and columns of a matrix in O(1) time?

Answer 1

Maybe numpy array can help you -- it allows to access both rows and columns and it's fairly efficient (it's the basic data type for scipy)

>>> def f(x,y):
...         return 10*x+y
...
>>> b = fromfunction(f,(5,4),dtype=int)
>>> b
array([[ 0,  1,  2,  3],
       [10, 11, 12, 13],
       [20, 21, 22, 23],
       [30, 31, 32, 33],
       [40, 41, 42, 43]])
>>> b[:,1]                                 # the second column of b
array([ 1, 11, 21, 31, 41])
>>> b[1:3,:]                               # the second and third row of b
array([[10, 11, 12, 13],
       [20, 21, 22, 23]])

Answer 2

You have to store your matrix either as a list of rows or list of columns. Which gives either swapping of rows or swapping of columns in O(1).

However, you can add another layer on top of it to handle column order so that you can reorder columns in O(1).

So for every access you need to do:

x = data[row][colorder[col]] 

Swap rows as:

data[row1], data[row2] = data[row2], data[row1]

And swap columns as:

colorder[col1], colorder[col2] = colorder[c2], colorder[c1]