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$.

  • $\begingroup$ 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}$? $\endgroup$
    – Raphael
    Oct 8, 2014 at 12:16
  • $\begingroup$ 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. $\endgroup$ Oct 8, 2014 at 15:23

1 Answer 1


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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.