Given a square grid of size $n\times n$ and $m$ symbols (say for example, alphabets A, B, C...), having $N(i)$ number of $i$th symbol; $\sum_{i=1}^{m}N(i) = n\times n$. Is there any computationally tractable algorithm that can be used to distribute the symbols uniformly inside the grid?

Uniform distribution here could be "shortest-distance-pairs have similar values". An example with 3 symbols A,B,C with equal counts of 3 in a $3\times3$ grid, I would expect a distribution of something like $ \left[ \begin{array}{ccc} A & C & B \\ C & B & A \\ B & A & C \end{array} \right]$. There could be many possible solutions, but the algorithm is expected to give one of them. And one more thing I am looking for is, the algorithm place symbol(s) with count value of 1 at (or near) the center of the grid, rather than at the corners.

  • 1
    $\begingroup$ The first paragraph is too confusing. Can you break them up into different sentences? $\endgroup$ – Milind R Mar 2 '13 at 21:48
  • 1
    $\begingroup$ @Milind R: I try to put it in a bit simpler way here: There are m symbols with counts/frequencies $N_1,N_2,…,N_m$, where $\sum_{i=1}^{m}N(i) = n\times n$. The problem is to distribute these symbols in a square grid of $n \times n$ cells as uniformly as possible. Hope it is clear now! $\endgroup$ – Srij Mar 5 '13 at 11:08
  • $\begingroup$ Have you looked at mutually orthogonal latin squares? en.wikipedia.org/wiki/… $\endgroup$ – EngrStudent May 7 '13 at 23:19

Your Answer

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

Browse other questions tagged or ask your own question.