2
$\begingroup$

Suppose I have a matrix $m \times n$ with entry 0 or 1. Of course there is a possible $2^{m\times n}$ matrix. I want to sort all the matrices so that every two consecutive matrices are only 1 bit different, and the different ones must be neighboring. I can make the first 2 matrices arbitrarily, but the next matrix will depend on the previous matrix. For example 2 initial matrix is

$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$ and $\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$

The changed bit is $a_{22}$ from 0 to 1. The third possible matrix is

$\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$ or $\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$

Because neighbors $a_{22}$ are $a_{12}$ and $a_{21}$. Can not change $a_{11}$ because it is not neighboring $a_{22}$

I can use dynamic programming, but complexity problems will arise if $m, n$ is large enough. Is there maybe a better algorithm? Or special case?

This is one of examples output for $m = n = 2$

$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$

$\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$

$\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$

$\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$

$\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$

$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$

$\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$

$\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

$\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$

$\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$

$\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$

$\endgroup$
  • $\begingroup$ Can you please argue that it is always possible for general $m, n$ to have "consecutive change positions" differ by one column only or one row, only (even "allowing wraparound": for a 3×3 matrix, $a_{21}$ and $a_{23}$ would be neighbours, too). $\endgroup$ – greybeard Mar 3 at 10:10
  • $\begingroup$ @greybeard tbh i can't guarantee it. Yes you're right $a_{21}$ and $a_{23}$ are neighbors of $a_{22}$ in 3×3 matrix $\endgroup$ – L Lawliet Mar 3 at 10:37
  • $\begingroup$ a₂₁ and a₂₃ are neighbors of a₂₂ I tried to get at $a_{21}$ and $a_{23}$ being neighbours to each other (so every element has four neighbours, including "corner elements" like $a_{11}$. $\endgroup$ – greybeard Mar 3 at 10:59
  • $\begingroup$ @greybeard corner element has two neighbors. Edge element has three neighbors. a_12 and a_21 are the only neighbors of a_11 $\endgroup$ – L Lawliet Mar 3 at 13:12
  • $\begingroup$ Have you checked Wikipedia? It mentions many different Gray codes with various properties. $\endgroup$ – Yuval Filmus Mar 3 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.