1

Have a twodimensional grid and need a reproducible, random value for every integer coordinate on this grid. This value should be as unique as possible. In a grid of, let's say 1000 x 1000 it shouldn't occur twice.

To put it more mathematical: I'd need a function f(x, y) which gives an unique number no matter what x and y are as long as they are each in the range [0, 1000]

f(x, y) has to be reproducible and not have side-effects.

Probably there is some trivial solution but everything that comes to my mind, like multiplying x and y, adding some salt, etc. does not lead anywhere because the resulting number can easily occur multiple times. One working solution I got is to use a randomizer and simply compute ALL values in the grid, but that is too computationally heavy (to do every time a value is needed) or requires too much memory in my case (I want to avoid pre-computing all the values).

Any suggestions? Huge thanks in advance.

DragonGamer
  • 834
  • 3
  • 9
  • 27
  • Take a look at [this](https://stackoverflow.com/a/1011215/6311045) and [this one](https://stackoverflow.com/q/962802/6311045) –  Sep 21 '19 at 22:52
  • @FarhadMehrad Thanks for the suggestion, but from what I understand, that requires to keep the 1000 x 1000 values in memory what I'd like to avoid. – DragonGamer Sep 21 '19 at 22:55
  • Yes, of course it's a heavy data to keep, but it's way better than generating millions of unique values at runtime. Imagine you need to generate 10 unique numbers, there is no way to estimate how many times you should try to generate them. –  Sep 21 '19 at 23:00

1 Answers1

1

I would use the zero-padded concatenation of your x and y as a seed for a built-in random generator. I'm actually using something like this in some of my current experiments.

I.e. x = 13, y = 42 would become int('0013' + '0042') = 130042 to use as random seed. Then you can use the random generator of your choice to get the kind (float, int, etc) and range of values you need:

Example in Python 3.6+:

import numpy as np
from itertools import product

X = np.zeros((1000, 1000))
for x, y in product(range(1000), range(1000)):
    np.random.seed(int(f'{x:04}{y:04}'))
    X[x, y] = np.random.random()

Each value in the grid is randomly generated, but independently reproducible.

Energya
  • 2,623
  • 2
  • 19
  • 24
  • 1
    Oh that is smart! Simple and smart, neat. This will probably be the solution, thank you! Will probably mark the question as solved. – DragonGamer Sep 21 '19 at 22:56