Evenly distributing integers in a grid

SLAM: debunk creationism, pseudoscience, and superstitions. Discuss logic and morality.

Moderator: Alyrium Denryle

Post Reply
User avatar
Exonerate
Sith Marauder
Posts: 4454
Joined: 2002-10-29 07:19pm
Location: DC Metro Area

Evenly distributing integers in a grid

Post by 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?

BoTM, MM, HAB, JL
User avatar
Surlethe
HATES GRADING
Posts: 12267
Joined: 2004-12-29 03:41pm

Re: Evenly distributing integers in a grid

Post by Surlethe »

*ears tingle*

I'll think about this and see if I can come up with a good answer over lunch.
A Government founded upon justice, and recognizing the equal rights of all men; claiming higher authority for existence, or sanction for its laws, that nature, reason, and the regularly ascertained will of the people; steadily refusing to put its sword and purse in the service of any religious creed or family is a standing offense to most of the Governments of the world, and to some narrow and bigoted people among ourselves.
F. Douglass
User avatar
Surlethe
HATES GRADING
Posts: 12267
Joined: 2004-12-29 03:41pm

Re: Evenly distributing integers in a grid

Post by 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). :)
A Government founded upon justice, and recognizing the equal rights of all men; claiming higher authority for existence, or sanction for its laws, that nature, reason, and the regularly ascertained will of the people; steadily refusing to put its sword and purse in the service of any religious creed or family is a standing offense to most of the Governments of the world, and to some narrow and bigoted people among ourselves.
F. Douglass
User avatar
Surlethe
HATES GRADING
Posts: 12267
Joined: 2004-12-29 03:41pm

Re: Evenly distributing integers in a grid

Post by 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.
A Government founded upon justice, and recognizing the equal rights of all men; claiming higher authority for existence, or sanction for its laws, that nature, reason, and the regularly ascertained will of the people; steadily refusing to put its sword and purse in the service of any religious creed or family is a standing offense to most of the Governments of the world, and to some narrow and bigoted people among ourselves.
F. Douglass
User avatar
Exonerate
Sith Marauder
Posts: 4454
Joined: 2002-10-29 07:19pm
Location: DC Metro Area

Re: Evenly distributing integers in a grid

Post by 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.

BoTM, MM, HAB, JL
User avatar
Grog
Padawan Learner
Posts: 290
Joined: 2002-07-18 11:32am
Location: Sweden

Re: Evenly distributing integers in a grid

Post by 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.
User avatar
Grog
Padawan Learner
Posts: 290
Joined: 2002-07-18 11:32am
Location: Sweden

Re: Evenly distributing integers in a grid

Post by Grog »

Grog wrote: 2018-09-04 05:04am 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.
:oops:
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
:oops:
User avatar
LaCroix
Sith Acolyte
Posts: 5193
Joined: 2004-12-21 12:14pm
Location: Sopron District, Hungary, Europe, Terra

Re: Evenly distributing integers in a grid

Post by 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
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.
Post Reply