Evenly distributing integers in a grid

[Exonerate]

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?

[Surlethe]

*ears tingle*

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

[Surlethe]

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:

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)

Bonus: once you've implemented this, if you haven't cooked up a proof yet, you can numerically test the proposition in (1).

[Surlethe]

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.

[Exonerate]

No worries, I appreciate you taking a crack at it

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}.

*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.

(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."

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.

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?

(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:

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.

[Grog]

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.

[Grog]

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.

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]

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