Create random sequence of integers within a range and with a minimum distance between them [closed]

Question

What is the fastest way to generate a specific nr of integers of random value uniformly distributed within a specific range and with a minimum distance between each element?

For example, given a sequence range between 0 and 20, we want to create 5 elements with at least 3 points distance between each element, the result could be something like this [0,5,11,14,19] or [2,5,9,13,18]

I created a loop that achieves this but it is very slow when i want to create ranges in the order of millions.

Answer 1

How about the following recipe: If you want a gap of 3 between your 5 adjacent elements, but want a total range of 20, then you effectively have 20 - (5-1)*3 steps of "slack" that you can randomly distribute in the gaps between your elements. Suppose we generate a number in that range, and scatter it between the elements, then we end up with code something like the following:

import numpy, random

n = 5
limit = 20
mingap = 3

slack = 20 - mingap * (n - 1)

def generate():
    steps = random.randint(0, slack)

    increments = numpy.hstack([numpy.ones((steps,)), numpy.zeros((n,))])
    numpy.random.shuffle(increments)

    locs = numpy.argwhere(increments == 0).flatten()
    return numpy.cumsum(increments)[locs] + mingap * numpy.arange(0, n)

If you then invoke this generate() function ten times, you get a collection of vectors something like the following:

[  0.   3.   6.   9.  12.]
[  0.   3.   6.  10.  13.]
[  2.   5.   8.  12.  15.]
[  1.   4.   7.  12.  16.]
[  0.   4.   7.  10.  13.]
[  0.   3.   6.   9.  12.]
[  1.   4.   9.  12.  16.]
[  0.   7.  10.  13.  16.]
[  0.   5.   8.  11.  14.]
[  1.   4.   8.  11.  17.]

Answer 2

This:

np.cumsum(np.ones((5,), np.int) * 3 + np.random.randint(0, maxn, (5,))) - 3

will give you 5 random numbers spaced by at least 3 points.

You have to tweak maxn to get the correct maximum value of the random numbers. Perhaps you may want to have a slightly bigger maxn and the reject samples whose elements exceed your maximum value (20).

Note: you didn't say what final distribution you are looking for, e.g. if you want the resulting samples uniformly distributed over the space of the valid samples, or anything else, if that matters.