Let $[N]$ denote the set $\{1,2, \ .. . \ ,N\}$ . For any $n,m \in \mathbb N$ what are some functions which traverse the grid $[n]\times[m]$, hitting each element exactly once? In particular, it would be nice to get a closed expression, for example, $(a,b)$ could be mapped to the binary number obtained by interleaving the bits of $a$ with $b$. But seems to only work when both $a$ and $b$ are powers of two. Please allow any extra assumptions if needed, and correct me if I'm wrong. Thank you.
4
-
2$\begingroup$ So you want a bijection $[n]\times[m] \to [n\times m]$? $\endgroup$– Naïm FavierCommented Jun 7 at 17:51
-
1$\begingroup$ Would the identity map $f:[n]\times[m]\to[n]\times[m]$ suffice? If not, there's also $f(x,y)=(p_1x,p_2y)$ where $f:[n]\times[m]\to\mathbb{Z}/n\mathbb{Z}$ and $\text{gcd}(p_1,n)=\text{gcd}(p_2,m)=1$ composed by natural inclusion $\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}\to[n]\times[m]$. $\endgroup$– JAG131Commented Jun 7 at 17:52
-
1$\begingroup$ The obvious traversal order is $(a, b) \mapsto a + bn$ (using 0-indexing rather than 1-indexing). $\endgroup$– Naïm FavierCommented Jun 7 at 17:54
-
$\begingroup$ @NaïmFavier, Thanks, both the answers work. $\endgroup$– PD_SathyaCommented Jun 7 at 17:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
An obvious example would be the trivial function $f:[n]\times[m]\to[n]\times[m]$ where $f(a,b)=(a,b).$
More generally (in case you're looking for something a bit more complicated), another answer could be $g=i\circ f_{(p_1,p_2)}$ where $f(x,y)=(p_1x,p_2y),\ f:[n]\times[m]\to\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}$, $\text{gcd}(p_1,n)=\text{gcd}(p_2,m)=1$ and $i:\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}\to[n]\times[m]$ denotes natural inclusion.
-
1$\begingroup$ Thanks, as mentioned in the other comment, I was looking for a bijection, (which is evident from writing a grid and enumerating) but I wanted a nice path traversal, which you gave. $\endgroup$ Commented Jun 7 at 18:01