[This algorithm puzzle was inspired by some Russian math contest problem I saw a long time back]
You have an $n \times n$ matrix of integers which you want to sort by columns: each column must be individually sorted in ascending order, the first row containing the smallest elements of each column.
There is a problem though, the only operation you are allowed to perform on the matrix, is to permute the elements of an individual row. That is you can pick one row, then permute the elements within that row. Then pick another row, permute the elements within that row etc. Each row could be permuted differently.
For example:
Say you are given the matrix:
$\begin{bmatrix}4&5&6\\1&3&2\\9&7&8\end{bmatrix}$
No matter how you permute the elements of the rows, the columns cannot be sorted.
If the matrix was
$\begin{bmatrix}3&1&7\\8&6&5\\9&7&8\end{bmatrix}$
Then you could shuffle just the first row (swap $3$ and $7$) so that it now looks like
$\begin{bmatrix}7&1&3\\8&6&5\\9&7&8\end{bmatrix}$
The columns are sorted: $[7,8,9], [1,6,7], [3,5,8]$
The puzzle is to come up with a polynomial time algorithm, which given the $n\times n$ matrix, tells if you could shuffle some rows (individually) so that the columns end up being sorted. The algorithm just has to give a Yes/No answer and not the actual permutations of the rows.
[Solution]
You have an $n \times n$ matrix of integers which you want to sort by columns: each column must be individually sorted in ascending order, the first row containing the smallest elements of each column.
There is a problem though, the only operation you are allowed to perform on the matrix, is to permute the elements of an individual row. That is you can pick one row, then permute the elements within that row. Then pick another row, permute the elements within that row etc. Each row could be permuted differently.
For example:
Say you are given the matrix:
$\begin{bmatrix}4&5&6\\1&3&2\\9&7&8\end{bmatrix}$
No matter how you permute the elements of the rows, the columns cannot be sorted.
If the matrix was
$\begin{bmatrix}3&1&7\\8&6&5\\9&7&8\end{bmatrix}$
Then you could shuffle just the first row (swap $3$ and $7$) so that it now looks like
$\begin{bmatrix}7&1&3\\8&6&5\\9&7&8\end{bmatrix}$
The columns are sorted: $[7,8,9], [1,6,7], [3,5,8]$
The puzzle is to come up with a polynomial time algorithm, which given the $n\times n$ matrix, tells if you could shuffle some rows (individually) so that the columns end up being sorted. The algorithm just has to give a Yes/No answer and not the actual permutations of the rows.
[Solution]
No comments:
Post a Comment