pythonmatrixcache-oblivious# Recursive Matrix Transposition in python

I am implementing a recursive approach for Matrix transposition as cache-oblivious algorithm. I have a problem when doing transpose and swap, the problem is when the matrix has odd number of columns:

**1 2 3
4 5 6
7 8 9**

The number 5 is in 2 smaller matrices that are created by recursive calls

2 3

**5** 6

&

4 **5**

7 8

This makes it **double swap** during recursive calls. I do not want to use any structure to store swapped items.

Is there a way to handle this double swapping problem?

Here is the implementation of mentioned methods.

```
class Matrix:
def __init__(self, N):
self.N = N
def transpose(self):
self._transpose(0, 0, self.N)
def _transpose(self, start_row, start_col, size):
if size == 1:
return # Base case: do nothing for a 1x1 matrix
first_half_size = size // 2
second_half_size = size - first_half_size
# Transpose the diagonal quadrants
self._transpose(start_row, start_col, first_half_size)
self._transpose(start_row + second_half_size, start_col + second_half_size, first_half_size)
# Transpose swap the off-diagonal quadrants
self._transpose_swap(start_row, start_col + first_half_size, start_row + first_half_size, start_col, second_half_size)
def _transpose_swap(self, start_row1, start_col1, start_row2, start_col2, size):
if size == 1:
# Base case: swap items
self.swap(start_row1, start_col1, start_row2, start_col2)
else:
first_half_size = size // 2
second_half_size = size - first_half_size
self._transpose_swap(start_row1, start_col1, start_row2, start_col2, first_half_size)
self._transpose_swap(start_row1, start_col1 + first_half_size, start_row2 + first_half_size, start_col2, second_half_size)
self._transpose_swap(start_row1 + first_half_size, start_col1, start_row2, start_col2 + first_half_size, second_half_size)
self._transpose_swap(start_row1 + second_half_size, start_col1 + second_half_size, start_row2 + second_half_size, start_col2 + second_half_size, first_half_size)
```

Solution

This worked. If two matrices will share a item, swap it.

```
def _transpose_swap(self, start_row1, start_col1, start_row2, start_col2, size):
if size == 1:
# Base case: swap items
self.swap(start_row1, start_col1, start_row2, start_col2)
else:
## ADDED --- Swap if two matrices share item
if size // 2 != (size+1) // 2:
self.swap(start_row1 + size // 2, start_col1 + size // 2, start_row2 + size // 2, start_col2 + size // 2)
# ---------------
first_half_size = size // 2
second_half_size = size - first_half_size
self._transpose_swap(start_row1, start_col1, start_row2, start_col2, first_half_size)
self._transpose_swap(start_row1, start_col1 + first_half_size, start_row2 + first_half_size, start_col2, second_half_size)
self._transpose_swap(start_row1 + first_half_size, start_col1, start_row2, start_col2 + first_half_size, second_half_size)
self._transpose_swap(start_row1 + second_half_size, start_col1 + second_half_size, start_row2 + second_half_size, start_col2 + second_half_size, first_half_size)
```

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?