1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ It should be 7%5, 7//5 or x%n, x//n in general for side length $n$. $\endgroup$ – orlp Jun 27 '18 at 1:14
  • 1
    $\begingroup$ 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$$ $\endgroup$ – InterstellarProbe Jun 27 '18 at 1:24
  • $\begingroup$ how did you design this particular function? $\endgroup$ – Matt Jun 27 '18 at 1:59
  • $\begingroup$ @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}$ $\endgroup$ – InterstellarProbe Jun 27 '18 at 2:07
  • $\begingroup$ Edit: probably unique. I thought the theorem was proven. Apparently it is still open. $\endgroup$ – InterstellarProbe Jun 27 '18 at 2:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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