0
$\begingroup$

Is there a formal algorithm to arrange a set of "numbers" on a grid/plane such that each adjacent set differs from the other by only one value. Something similar to the Grey code but further extended or are we forced to go to multi-dimesnions?,

To make things clear, suppose we have a set comprised of $M$ numbers in the form of $(m_1,m_2,m_3)$, each digit can take up to the value $N$ where $N$ is always a single digit number. As an example suppose $M = 3$ and $N = 3$ therefore all the possible combinations are:

(0,0,0),(0,0,1),(0,0,2),(0,0,3),(1,0,0),(1,0,1),(1,0,2),(1,0,3)
(0,1,0),(0,1,1),(0,1,2),(0,1,3),(1,1,0),(1,1,1),(1,1,2),(1,1,3)
(0,2,0),(0,2,1),(0,2,2),(0,2,3),(1,2,0),(1,2,1),(1,2,2),(1,2,3)
(0,3,0),(0,3,1),(0,3,2),(0,3,3),(1,3,0),(1,3,1),(1,3,2),(1,3,3)     
(2,0,0),(2,0,1),(2,0,2),(2,0,3),(3,0,0),(3,0,1),(3,0,2),(3,0,3)
(2,1,0),(2,1,1),(2,1,2),(2,1,3),(3,1,0),(3,1,1),(3,1,2),(3,1,3)
(2,2,0),(2,2,1),(2,2,2),(2,2,3),(3,2,0),(3,2,1),(3,2,2),(3,2,3)
(2,3,0),(2,3,1),(2,3,2),(2,3,3),(3,3,0),(3,3,1),(3,3,2),(3,3,3)

I need this because in what I am doing, each set has a corrosponding value and I need to plot those values and serach for maxima/minima later on. Thanks.

P.S. Are there any limitations on the shape? (i.e. square) or could it take any form (cross, rectangle)? Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

If "neighbour" is one step in one dimension then the problem is trivially separable. Each axis has its own orthogonal 1-d Gray code.

If you have any larger set of neighbours then it will be impossible unless you embed suitably in a higher dimension (i.e. increase the M) - the proof is simply that Gray has optimal close-packing.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .