# 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[0]))
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

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 rowafter 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
})
```

(`zip()`

in conjunction with the `*`

operator can be used to unzip a list.)

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(

nm)

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!