Enumerating the elements of an integer lattice $\mathbb{Z}^n$

The elements of $\mathbb{Z}$ can be enumerated as $0, 1, -1, 2, -2, 3, -3, \ldots$. Similarly, the points of the lattice $\mathbb{Z}^2$ can be enumerated

$$(0,0), (1,0), (0,1), (-1,0), (0,-1), (2,0), (1,1), (0,2), (-1,1), \ldots$$

I would like to extend this algorithm to $\mathbb{Z}^n$. Is there a simple way to do that?

Note that the ordering of the elements may vary. The only condition should be that if $B_1$ and $B_2$ are two closed balls in the metric $L^1$ on $\mathbb{Z}^n$, and $B_1 \subset B_2$, then all the elements of $B_1$ should be enumerated before any element of $B_2 - B_1$.

• So you have a mapping from $\mathbb{Z^2}$ into $\mathbb{N}$; what prevents you from using it to map $\mathbb{Z^3} = \mathbb{Z} \times \mathbb{Z^2}$ into $\mathbb{N}$? Commented Oct 8, 2014 at 12:16
• Nothing. Everybody knows that $\mathbb{Z}^n$ is enumerable, so I am not asking for a proof of the enumerability of $\mathbb{Z}^n$. I want to have an explicit construction of the bijection. FrankW has given a recursive algorithm below. That's OK, but I would prefer a non-recursive one, if possible. Commented Oct 8, 2014 at 15:23

Your additional condition requires the tuples to be listed in ascending order of the sum of the absolute value of their components. We are free to choose the order of tuples with the same sum, so I propose the following procedure:

list(k,n) lists the $k$-tuples, where the absolute values sum to $n$:

For i=n downto -n:
Output all outputs of list(k-1,n-|i|), each prefixed by i.


list(k) lists all $k$-tuples:

n=0;
While true:
Output all outputs of list(k,n).
n++.

• Do you mean $n+1$ recursive calls to list(k-1, n-|i|) ? Commented Oct 8, 2014 at 11:09
• $2n+1$ calls, actually. (With different $i$ each time, of course.) Commented Oct 8, 2014 at 11:10
• OK, thanks, I will check that, and I will get back to you if necessary. Commented Oct 8, 2014 at 11:18