algorithm - Build a directed regular graph of elements in an array -

given array, able define relationship between elements each element "points to" given number of elements, such no element should share more 1 target element other given element of array.

i'm pretty sure can done solution graph theory, embarrassingly don't know graph theory , therefore don't know i'm looking for. best can graph describing links between elements regular , directed.

the xy: have/want two-dimensional grid (i don't think dimension relevant math helpful visualization), each cell points around 16 (flexible on this) other cells minimum of duplication. grid texture it's anywhere in 256*256 4096*4096 size range, doesn't make significant difference algorithm.

once visualized 2d texture, there obvious "intuitive" solution based on image masks, it's totally informal , relies on implementation details (using fewer targets purposes of illustration):

1. using regular pattern pointed-to cells inappropriate:

   

   the next cell along share seven targets origin cell (red, x). duplication guaranteed.

2. an irregular "broken circle" style arrangement intuitively seems should work:

   

   if no pair of cells in group (pointed-to , origin) have equal difference in position other pair of cells in group, given movement of origin on grid seems shouldn't result in more 1 pointed-to cell overlapping of highlighted in original position, , none of pointed-to (blue) cells should point origin (red, x) directly (it nice if didn't loop quickly, either).

("wrapping around" @ edges of texture assumed)

but totally informal , intuitive. don't have proof of , don't know how go proving it. there algorithm known graph theory can produce such result, without wishy-washy handwaving involving image masks? not least because intuitive solution, assuming works, doesn't provide guarantees whether target cells loop origin or not, , whether entire grid (or of it, don't mind few unused cells) forms single connected graph, absolutely essential.

alternatively, if "broken circle" model works, how 1 go formalizing down abstract algorithm operating on sequence (i guess it's integer sequence), rather relying on mask image, totally getting confused implementation details? (the fact want apply to texture should irrelevant)

the mathematical description of want build (strongly?) connected high-girth cayley graph on group z/w × z/h (where w width of texture , h height) such no 2 vertices have more 1 out-neighbor in common.

practically speaking, each vertex (i.e., pixel) points pixels @ fixed list of offsets. if vertex @ (0, 0) (w.l.o.g. vertex-transitivity of cayley graphs) , vertex @ (x, y) have 2 out-neighbors in common, there exist offsets (dx1, dy1), (dx2, dy2), (dx3, dy3), (dx4, dy4) such (dx1, dy1) = (x + dx2, y + dy2) , (dx3, dy3) = (x + dx4, y + dy4), , (dx1, dy1) ≠ (dx3, dy3) (equivalently, (dx2, dy2) ≠ (dx4, dy4)). condition can verified programmatically, , random sets of offsets within close distance, doesn't take long find suitable set. here's python generate , test them.

from random import randrange  # random pattern of offsets within square [-k, k] x [-k, k] def pattern(k, n):     return [(randrange(-k, k + 1), randrange(-k, k + 1)) in range(n)]  def valid(pat):     s = set()     (x1, y1) in pat:         (x2, y2) in pat:             if ((x1, y1) != (x2, y2)):                 (dx, dy) = (x2 - x1, y2 - y1)                 if (dx, dy) in s:                     return false                 s.add((dx, dy))     return true  if __name__ == '__main__':     while true:         pat = pattern(10, 16)         if valid(pat):             break     print(pat) 

this code not verify strong connectivity. conjecture strong connectivity satisfied random offset sets. might want write more code check short cycles, can found breadth-first search.

the code above gives list of offsets like

[(3, -4), (-8, -9), (2, 7), (-9, 3), (-4, 7), (-2, -7), (-6, 3), (-7, -2), (9, -10), (8, -2), (-6, -3), (2, -8), (-6, 6), (-9, -7), (-7, 10), (3, 10)] 

(no idea if one's good). figure out vertices (x, y) points to, iterate (dx, dy) through list above , yield neighbor ((x + dx) & (w - 1), (y + dy) & (h - 1)), assuming w , h powers of 2 , we're two's complement.