How to make a random selection keeping minimum distance between values

General Usage
1 
m = 100
n = 10
b = rand(1:m,n)
b = sort(b)

I want the minimum distance between adjacent values of b to be >= 2.
How can I do that.
I have tried

b = rand(1:m,n)                    
											
	while  true 
		if length(Set(b)) == length(b)			
			
			b = sort(b)
			c = diff(b)
			if true == all(i -> i >= 2,c)
				break
			end
		else
			b = rand(1:m,n)
		end
	end

But this is taking a long time (almost infinite loop)

2

I have found out an answer by adapting python code to julia :

a = [2*i + x for (i, x) in enumerate(sort!(rand(1:m, n)))]

but these values are going above m.

3

Fundamentally there may not be n numbers in the range 1:m with minimum difference 2. And when m >> n it’s not clear precisely what distribution you want the numbers to come from.

That being said, a slightly better approach would be to generate the differences, perhaps from a geometric distribution:

using Distributions
p = 0.5
while true
  b = cumsum(rand(Geometric(p), n) .+ 2)
  last(b) <= m && break
end

Adjusting p will give different distributions, and large p and/or 2n close to m will result in the loop running longer.

1 Like
4

As screw_dog pointed out, this depends on what kind of randomness you want.
But if you simply want to keep the maximum value below m, why not just use (1-k):(m-k*n) instead of 1:m?

k = 2
[k*i + x for (i, x) in enumerate(sort!(rand((1-k):(m-k*n), n)))]
2 Likes