# Solving the Row-Column Exchange problem using Python

By John Lekberg on January 22, 2020.

This week's post is about solving an interview question: the "Row-Column Exchange" problem. You will learn

• how to solve this problem using a brute force algorithm,
• why the brute force algorithm scales poorly, and
• how to solve this problem using a more efficient algorithm.

# Problem statement

Cam you transform this table

`````` 1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
``````

into this table

``````12 10 11  9
16 14  5 13
8  6  7 15
4  2  3  1
``````

by only exchanging rows and columns?

Here's what I mean by "row exchange" and "column exchange". Starting with this table

`````` 1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
``````

Here is a row exchange that swaps rows 1 and 3 of the original table:

`````` 9 10 11 12  *
5  6  7  8
1  2  3  4  *
13 14 15 16
``````

And here is a column exchange that swaps columns 3 and 4 of the original table:

``````       *  *
1  2  4  3
5  6  8  7
9 10 12 11
13 14 16 15
``````

# Solving with brute force

Solving this problem using a brute force algorithm will involve generating every possible combination of row exchanges and column exchanges.

How many combinations are there? First, I notice that row exchanges and column exchanges commute. What I mean is that

swapping rows 1 and 2, then swapping columns 3 and 4.

has the same effect as

swapping columns 3 and 4, then swapping rows 1 and 2.

This means that any combination of row exchanges and column exchanges can be grouped into

• a group of row exchanges, which creates a row permutation, and
• a group of column exchanges, which creates a column permutation.

This problem uses a grid with 4 rows and 4 columns. There are 24 (4!) possible row permutations and 24 possible column permutations, which means that there are 576 (24 * 24) possible pairs of row permutations and columns permutations.

The number of combinations that I need to check is small enough that using a brute force algorithm is feasible. Here's a Python implementation:

``````from itertools import permutations, product

def brute_force_search(A, B):
row_indices = range(len(A))
col_indices = range(len(A))

all_possibilities = product(
permutations(row_indices),
permutations(col_indices),
)
for row_p, col_p in all_possibilities:
is_solution = all(
A[row_p[i]][col_p[j]] == B[i][j]
for i, j in product(row_indices, col_indices)
)
if is_solution:
return row_p, col_p
``````

This code uses itertools.permutations to generate row permutations and columns permutations, and uses itertools.product to generate all combinations of row permutations and column permutations.

Now I need to define the two grids from the problem statement:

``````A = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]

B = [
[12, 10, 11, 9],
[16, 14, 5, 13],
[8, 6, 7, 15],
[4, 2, 3, 1]
]
``````

The brute force search shows that there is no way to exchange rows and columns to turn one of the grids into the other:

``````brute_force_search(A, B) or "no solution found"
``````
``````'no solution found'
``````

# A more efficient algorithm

The brute force search algorithm scales poorly. For grids with n rows and m columns, this algorithm has a time complexity of

O(n! m! n m)

This means that a brute force search on a pair of 7 by 7 grids will take about 135,000 times longer than on a pair of 4 by 4 grids. (To put that in perspective, if searching 4 by 4 grids takes 1 second, then searching 7 by 7 grids will take about 38 hours.)

To create a faster algorithm, I will create a canonical form for each grid and check if the canonical forms are equal. The goal of this is:

grids that can be turned into each other by row exchanges and column exchanges have the same canonical form.

To design a canonical form, I start by looking a simpler version of this problem: checking one dimensional lists (instead of two dimensional grids). Consider lists `a` and `b`:

``````a = [1, 1, 1, 3, 3, 2]
b = [3, 2, 1, 1, 3, 1]
``````

To check if `a` and `b` are permutations of each other, I care about what elements they have, but not the order that the elements are in. I'll use a collections.Counter object (a built-in implementation of multisets) to compare the two lists:

``````from collections import Counter

Counter(a)
``````
``````Counter({1: 3, 3: 2, 2: 1})
``````
``````Counter(b)
``````
``````Counter({3: 2, 2: 1, 1: 3})
``````
``````Counter(a) == Counter(b)
``````
``````True
``````

This design can be extended to a grid by using both

• a multiset of row multisets, and
• a multiset of column multisets.

The intuition behind this is that

things in the same row stay in the same row after a row exchange or a column exchange (even though the ordering of the row may change).

(The same is true of things in the same column.)

Here's a Python function that generates a multiset of row multisets for a grid:

``````def row_multisets(grid):
hashable_Counter = lambda x: frozenset(Counter(x).items())
return Counter(hashable_Counter(row) for row in grid)

grid = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]

row_multisets(grid)
``````
``````Counter({
frozenset({(1, 1), (2, 1), (3, 1), (4, 1)}): 1,
frozenset({(5, 1), (6, 1), (7, 1), (8, 1)}): 1,
frozenset({(9, 1), (10, 1), (11, 1), (12, 1)}): 1,
frozenset({(13, 1), (14, 1), (15, 1), (16, 1)}): 1
})
``````

I use a frozenset because collections.Counter isn't hashable (it's mutable). Since collections.Counter is a subclass of dict and dictionaries require that keys are hashable, I can't directly create a collections.Counter that counts unhashable objects.

``````Counter(Counter(row) for row in grid)
``````
``````Traceback (most recent call last):
...
TypeError: unhashable type: 'Counter'
``````

Because I don't need to modify the collections.Counter objects once I have created them, an easy workaround for this problem is to turn the collections.Counter into a frozenset of tuples, which is hashable.

To generate a multiset of columns multisets, I can reuse `row_multisets` by transposing the grid and generating the multiset of row multisets. (The rows of the transpose are the columns of the original.)

``````def transpose(grid):
return list(map(list, zip(*grid)))

def column_multisets(grid):
return row_multisets(transpose(grid))

column_multisets(grid)
``````
``````Counter({
frozenset({(1, 1), (5, 1), (9, 1), (13, 1)}): 1,
frozenset({(2, 1), (6, 1), (10, 1), (14, 1)}): 1,
frozenset({(3, 1), (7, 1), (11, 1), (15, 1)}): 1,
frozenset({(4, 1), (8, 1), (12, 1), (16, 1)}): 1
})
``````

Here's how to define a canonical form, using `row_multisets()` and `column_multisets()`:

``````def canonical_form(grid):
return row_multisets(grid), column_multisets(grid)
``````

And given the two grids from the problem statement:

``````A = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]

B = [
[12, 10, 11, 9],
[16, 14, 5, 13],
[8, 6, 7, 15],
[4, 2, 3, 1]
]
``````

I compare the canonical forms and confirm that they don't match:

``````canonical_form(A) == canonical_form(B)
``````
``````False
``````

For grids with n rows and m columns, computing the canonical form has a time complexity of

O(n m)

So this method scales much better than the brute force search.

# In conclusion...

Brute force solutions may not scale well, but they are usually easy to implement. Learning how to estimate the viability of a brute force approach is a useful skill. When a brute force technique is not good enough, consider representing your data in a different way (e.g. a canonical form) to allow for a more efficient algorithm.

Here's my challenge to you:

Try to design another canonical form (instead of a multiset of multisets) that allows you to create another efficient solution to the "Row-Column Exchange" problem.

If you enjoyed reading this, share it with your friends and stay tuned for next week's post. See you then!