ansaurus

Question

Generating a perfectly distributed grid from array

Answer 1

+1 A:

You could pick a number (say k) relatively prime to n (and perhaps close to n/2 or sqrt(n) or whatever you like), and keep shifting by k.

For eg n = 8. Pick k = 3. You get

A B C D E F G H
F G H A B C D E
C D E F G H A B
H A B C D E F G
E F G H A B C D 
B C D E F G H A
G H A B C D E F
D E F G H A B C

I have assumed you don't want to see same rows appear again.

Does that work for you?

Also these might help: Latin Squares.

Moron 2010-06-16 22:57:06

Thanks for your feedback! I wrote a small program to try this model out. Sometimes it works great, but about half of the times it doesn't. I used n=19, letters A through S (but replaced the letter A with the apple logo  to make it stand out more). I plotted the grid using k=10 and what becomes visibile are two diagonal lines of apple logos. The apples didn't spread out evenly across the grid.

zath 2010-06-17 18:13:20

@zath: I suggest using k closer to sqrt(n). In this case for n=19, k=4 or 5 might work out well.

Moron 2010-06-17 20:23:25

Wow, you are right. Using a k-value near sqrt(n) works MUCH better. I just plotted a 49x49 grid using k=8 and the distrubution might actually be perfect. Do you know why it works so much better, or should I just shrug it off as magic? :-)

zath 2010-06-17 21:30:03

@zath. It takes approx n/k shifts to make a character get back close to its original position. So sqrt(n) is sort of the 'optimum' there. For instance k = sqrt(n) maximizes the value k + n/k and is big enough to not make the symmetry obvious.

Moron 2010-06-17 21:38:56

Answer 2

A:

As long as your array contains more than 4 letters, shifting them two to the right (like you did), will always produce results that don't touch each other. If you want some other amount, use the following guidelines.

The range of the shift amount should be within:

2 <= shift_amount <= (array.length - 2)

This is because to not "touch" a row above, a character must be at least 2 spaces away from it on the next row:

X X X X X
X X O X X
A X X X A

In this example, imagine that the O was already placed on that line. Now we need to generate the next line. The A's represent the closest points an O can be on the next line, which is 2 spaces away.

If you want the most distribution (i.e. the numbers spaced out the most) you should choose the number in the middle of this range (e.g. 3 for 6, 3 or 4 for 7, etc.).

Here are some more examples which are less about even distribution but more about if the numbers touch or not:

4x4 shifted by 2 (success): 2 <= 2 <= 2

A B C D
C D A B
A B C D
...

5x5 shifted by 3 (success): 2 <= 3 <= 3

A B C D E
D E A B C
B C D E A
E A B C D
C D E A B

5x5 shifted by 4 (failure): 2 <= 4 <!= 3

A B C D E
E A B C D
D E A B C
C D E A B
B C D E A

6x6 shifted by 2 (success): 2 <= 2 <= 4

A B C D E F
C D E F A B
E F A B C D
...

26x26 shifted by 2 (success): 2 <= 2 <= 24

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
...

Senseful 2010-06-16 23:01:18

Thanks for your feedback. I tried this model using your suggestion for most distrubution (choosing a number in the middle the range). The characters are indeed spaced far away from each other, but only on the x-axis. I'll update my question to show how this scenario played out.

zath 2010-06-17 20:23:22

ansaurus

tags:

views:

answers:

Generating a perfectly distributed grid from array

related questions