# Given a square grid of side length N and m objects, design a bijection between each object and a unique set of coordinates

Given a square grid of side length N and m objects, can I design a 1-1 relationship between each object and a unique set of coordinates in that 2-D plane?

Imagine the context being something like storing objects in a hashmap of id to object and needing to calculate the L1 norm / Manhattan distance between any two objects quickly.

My initial thought was to use the mod operator and floor division, e.g. if we have $10$ objects and a $5$ by $5$ grid, maybe the unique location of object 7 will be $(25 \% 7, 25 // 7)$ = $(4, 3)$?

I'm less interested in an answer than I am in the thinking / creative process used to come up with a solution, and how to prove the answer is correct or disprove such a function exists.

Thank you!

• It should be 7%5, 7//5 or x%n, x//n in general for side length $n$. – orlp Jun 27 '18 at 1:14
• It is definitely possible. There exists a one-to-one mapping between $\mathbb{N}^2$ and $\mathbb{N}$ so there are definitely plenty of mappings between arbitrary grids and a subset of the natural numbers. $$(m,n)\mapsto \dfrac{(m+n)(m+n+1)}{2}+m$$ – InterstellarProbe Jun 27 '18 at 1:24
• how did you design this particular function? – Matt Jun 27 '18 at 1:59
• @Matt it is the Cantor Pairing Function. en.m.wikipedia.org/wiki/Pairing_function. It turns out it is the unique quadratic bijection between $\mathbb{N}^2$ and $\mathbb{N}$ – InterstellarProbe Jun 27 '18 at 2:07
• Edit: probably unique. I thought the theorem was proven. Apparently it is still open. – InterstellarProbe Jun 27 '18 at 2:12

The problem with your idea is that the values may fall outside the square. Object $1$ will be at $(0,10)$ and object $9$ will be at $(7,2)$, both outside your $5 \times 5$ square. The simplest approach is to use the side of the square as the denominator, so object $n$ goes at $(n\%N,n//N)$. This just puts them in the first columns as far as you need to go.