## Evenly distributing integers in a grid

**Moderators:** Alyrium Denryle, SCRawl, Thanas

### Evenly distributing integers in a grid

I'm doing a hobby project and curious if there was an easy solution obvious to anybody with a deeper math background...

Say that I have a square grid with a side length of N, where N is a power of 2. I am going to fill this grid of N2 cells with N2 consecutive integers; one integer per cell.

Within this grid, I can select adjacent cells to form unique rectangles, ranging from a size of 1x1 to NxN. By unique, I refer to the combination of cells that are selected, not their dimensions. So, for a 2x2 grid, I have 9 unique rectangles (four 1x1 rectangles, two 2x1, two 1x2, and one 2x2). The number rectangles I can form rapidly explodes with the size of the grid (Σ N3).

Each selection of these rectangles contains a subset of the integers I've put in the grid. Some of these integers might be consecutive and will be grouped together. So, if I have a subset of {0, 5, 6, 7, 10, 11}, I would split them into {0}, {5, 6, 7}, and {10, 11}.

My goal is to find a way to distribute my integers in the grid in a way that will have them split as uniformly as possible when I select them by rectangles, over the range of all possible rectangles I can form. Intuitively, I'd say I should go through my list of integers and place them spaced N/2 from each other, since it's a stable equilibrium (Increasing the spacing inevitably "squeezes" my available space as I progress down the list). And after rotating through the 4 quadrants I can form, I'd displace a distance of N/4 and start again... But beyond that, I'm a little lost. Any ideas on how to achieve this?

Say that I have a square grid with a side length of N, where N is a power of 2. I am going to fill this grid of N2 cells with N2 consecutive integers; one integer per cell.

Within this grid, I can select adjacent cells to form unique rectangles, ranging from a size of 1x1 to NxN. By unique, I refer to the combination of cells that are selected, not their dimensions. So, for a 2x2 grid, I have 9 unique rectangles (four 1x1 rectangles, two 2x1, two 1x2, and one 2x2). The number rectangles I can form rapidly explodes with the size of the grid (Σ N3).

Each selection of these rectangles contains a subset of the integers I've put in the grid. Some of these integers might be consecutive and will be grouped together. So, if I have a subset of {0, 5, 6, 7, 10, 11}, I would split them into {0}, {5, 6, 7}, and {10, 11}.

My goal is to find a way to distribute my integers in the grid in a way that will have them split as uniformly as possible when I select them by rectangles, over the range of all possible rectangles I can form. Intuitively, I'd say I should go through my list of integers and place them spaced N/2 from each other, since it's a stable equilibrium (Increasing the spacing inevitably "squeezes" my available space as I progress down the list). And after rotating through the 4 quadrants I can form, I'd displace a distance of N/4 and start again... But beyond that, I'm a little lost. Any ideas on how to achieve this?

BoTM, MM, HAB, JL

- Surlethe
- HATES GRADING
**Posts:**12248**Joined:**2004-12-29 03:41pm**Location:**Hiding a pot of gold at the end of the Ricci flow-
**Contact:**

### Re: Evenly distributing integers in a grid

*ears tingle*

I'll think about this and see if I can come up with a good answer over lunch.

I'll think about this and see if I can come up with a good answer over lunch.

*Keep, ancient lands, your storied pomp! Give me your tired, your poor, your huddled masses yearning to breathe free, the wretched refuse of your teeming shore. Send these, the homeless, tempest-tost to me. I lift my lamp beside the golden door!*

- Surlethe
- HATES GRADING
**Posts:**12248**Joined:**2004-12-29 03:41pm**Location:**Hiding a pot of gold at the end of the Ricci flow-
**Contact:**

### Re: Evenly distributing integers in a grid

Sorry, I forgot about this after work on Friday.

You have a grid G = {1,...,N}x{1,...,N} and you want to define a random bijective function f: G\to {1,...,N^2}.

(1) I don't have proof but am fairly certain that if your function is random then so will be any restriction, in some appropriate sense. The precise statement will be something like "if f is a random bijection, then the restriction of f to any subset will be a random injection."

(2) Let's riff on the hypothesis of that statement. What you're really trying to do is cook up a random bijection between G and {1,...,N^2}, right? So if you're looking for an algorithm, order G (lexicographically, say) and find an algorithm that generates random permutations. Google says one such is the Knuth shuffle. Or if you're using python, numpy.random.permutation:
Bonus: once you've implemented this, if you haven't cooked up a proof yet, you can numerically test the proposition in (1).

You have a grid G = {1,...,N}x{1,...,N} and you want to define a random bijective function f: G\to {1,...,N^2}.

(1) I don't have proof but am fairly certain that if your function is random then so will be any restriction, in some appropriate sense. The precise statement will be something like "if f is a random bijection, then the restriction of f to any subset will be a random injection."

(2) Let's riff on the hypothesis of that statement. What you're really trying to do is cook up a random bijection between G and {1,...,N^2}, right? So if you're looking for an algorithm, order G (lexicographically, say) and find an algorithm that generates random permutations. Google says one such is the Knuth shuffle. Or if you're using python, numpy.random.permutation:

Code: Select all

```
import numpy as np
def random_array(N):
initial_arr = np.arange(N**2).reshape((N,N))
return np.random.permutation(initial_arr)
```

*Keep, ancient lands, your storied pomp! Give me your tired, your poor, your huddled masses yearning to breathe free, the wretched refuse of your teeming shore. Send these, the homeless, tempest-tost to me. I lift my lamp beside the golden door!*

- Surlethe
- HATES GRADING
**Posts:**12248**Joined:**2004-12-29 03:41pm**Location:**Hiding a pot of gold at the end of the Ricci flow-
**Contact:**

### Re: Evenly distributing integers in a grid

Mulling on this, I think an appropriate definition of "random injection" is one where the probability of any point taking any value in the codomain is uniform. Then the proposition you want is straightforward: if f is a random permutation of a finite set S, then the probability of any point in S taking any value in S is uniformly distributed. That property doesn't change when you restrict f to a subset T of S, so if f is correctly defined then your property should hold for

*every*subset of {1,...,N}x{1,...,N}, not just subrectangles.*Keep, ancient lands, your storied pomp! Give me your tired, your poor, your huddled masses yearning to breathe free, the wretched refuse of your teeming shore. Send these, the homeless, tempest-tost to me. I lift my lamp beside the golden door!*

### Re: Evenly distributing integers in a grid

No worries, I appreciate you taking a crack at it

*Squints at Wikipedia* Yes, I'm looking for a bijective function. (You can probably tell I don't have any actual background in pure math). But I'm not sure I'm looking for a random one. I'm operating under the assumption that there is some deterministic way to distribute these integers. I'm guessing your thinking is that given a population of grids filled with (pseudo)randomly distributed integers, any "bad" distributions would get averaged out... but individual grids could still be bad, which is something I'd like to avoid. Is a uniform distribution/randomness the optimum? To be clear, I want to maximize the amount of sets of consecutive integers formed by selecting rectangles.You have a grid G = {1,...,N}x{1,...,N} and you want to define a random bijective function f: G\to {1,...,N^2}.

(1) I don't have proof but am fairly certain that if your function is random then so will be any restriction, in some appropriate sense. The precise statement will be something like "if f is a random bijection, then the restriction of f to any subset will be a random injection."

Let me repeat this back to make sure I'm interpreting it correctly - if the mapping of integers to the grid is random, then the integers in any rectangle selected will also be mapped randomly?Mulling on this, I think an appropriate definition of "random injection" is one where the probability of any point taking any value in the codomain is uniform. Then the proposition you want is straightforward: if f is a random permutation of a finite set S, then the probability of any point in S taking any value in S is uniformly distributed. That property doesn't change when you restrict f to a subset T of S, so if f is correctly defined then your property should hold for every subset of {1,...,N}x{1,...,N}, not just subrectangles.

Well, I'm not sure I'm looking for randomness... I also neglected to mention having something easily reversible so one could quickly determine what's in neighboring cells, given just the integer in our reference cell, is also important.(2) Let's riff on the hypothesis of that statement. What you're really trying to do is cook up a random bijection between G and {1,...,N^2}, right? So if you're looking for an algorithm, order G (lexicographically, say) and find an algorithm that generates random permutations. Google says one such is the Knuth shuffle. Or if you're using python, numpy.random.permutation:

BoTM, MM, HAB, JL

### Re: Evenly distributing integers in a grid

I don't think you are looking for anything random at all.

I sugest the following method (illustrated with three examples, I hope the patern is clear):

1 2

4 3

1 2 3 4

8 7 6 5

9 10 11 12

16 15 14 13

1 2 3 4 5 6 7 8

.....................9

.................

64 63 ..........

All rectangles split up into sets of the same size, can't get more uniform than that. But it is not clear to me that I understand what it is that you want.

I sugest the following method (illustrated with three examples, I hope the patern is clear):

1 2

4 3

1 2 3 4

8 7 6 5

9 10 11 12

16 15 14 13

1 2 3 4 5 6 7 8

.....................9

.................

64 63 ..........

All rectangles split up into sets of the same size, can't get more uniform than that. But it is not clear to me that I understand what it is that you want.

### Re: Evenly distributing integers in a grid

Grog wrote: ↑2018-09-04 05:04amI don't think you are looking for anything random at all.

I sugest the following method (illustrated with three examples, I hope the patern is clear):

1 2

4 3

1 2 3 4

8 7 6 5

9 10 11 12

16 15 14 13

1 2 3 4 5 6 7 8

.....................9

.................

64 63 ..........

All rectangles split up into sets of the same size, can't get more uniform than that. But it is not clear to me that I understand what it is that you want.

The patern with the desired property is of course

1 2

3 4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

1 2 3 4 5 6 7 8

9................

.................

..........63 64

- LaCroix
- Sith Marauder
**Posts:**4705**Joined:**2004-12-21 12:14pm**Location:**Sopron District, Hungary, Europe, Terra

### Re: Evenly distributing integers in a grid

you would need to optimize in 2 runs... x and y axis.

1 2

3 4

flip the second line

1 2

4 3

Nice, but with a second flip in Y

1 3

4 2

You get the near optimum result for 2x1 boxes...

But the system becomes less easy to do if you start with a bigger matrix

Double the size of X and Y:

Flip x:

1 2 3 4

8 7 6 5

9 10 11 12

16151413

flip every 2nd Y axis.

1 15 3 13

8 10 6 12

9 7 11 5

16 2 14 4

Now each 4x4 is 34.

pretty good, but the deviation starts adding up if you do not compare 2x2 rectangles but 1x2s.

Each time you increase your matrix, your resolution gets worse...

Maybe some clever diagonal flips would help

1 2

3 4

flip the second line

1 2

4 3

Nice, but with a second flip in Y

1 3

4 2

You get the near optimum result for 2x1 boxes...

But the system becomes less easy to do if you start with a bigger matrix

Double the size of X and Y:

Flip x:

1 2 3 4

8 7 6 5

9 10 11 12

16151413

flip every 2nd Y axis.

1 15 3 13

8 10 6 12

9 7 11 5

16 2 14 4

Now each 4x4 is 34.

pretty good, but the deviation starts adding up if you do not compare 2x2 rectangles but 1x2s.

Each time you increase your matrix, your resolution gets worse...

Maybe some clever diagonal flips would help

A minute's thought suggests that the very idea of this is stupid. A more detailed examination raises the possibility that it might be an answer to the question "how could the Germans win the war after the US gets involved?" - Captain Seafort, in a thread proposing a 1942 'D-Day' in Quiberon Bay

I do archery skeet. With a Trebuchet.

I do archery skeet. With a Trebuchet.