Return to Blog

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

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

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

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

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

(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(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!

(If you spot any errors or typos on this post, contact me via my contact page.)