Set random numbers in array with spacing

Question

I need to fill a Ruby array with N random numbers. However, I need to ensure that they are X numbers apart from each other.

For instance, I need to fill an array with 5 numbers, randomly generated between 1 and 100, but ensuring that no number is closer than 3.

So this is valid:

[1, 4, 7, 22, 84]  # the differences between the numbers are >= 3

This is not valid:

[1, 2, 50, 70, 90] # "1" and "2" are too close together

Any ideas?

Answer 1

Here's one idea: every time a random number is generated, remove every number that's close to it from the candidates:

def gen_rand_arr(arr, diff)
  sample = arr.sample
  arr.delete_if {|x| (x - sample).abs < diff }
  sample
end

Then use it like:

arr = (1..100).to_a
result = []
1.upto(5) { result << gen_rand_arr(arr, 3) }
p result.sort

Answer 2

i = 1
while i < 100  do
   final = rand(i+3..i+20)
   (a ||= []).push(final)
   i +=20
end
p a

---

Some random examples.

[18, 39, 48, 65, 83]
[9, 27, 56, 66, 100]
[10, 29, 46, 68, 86]
[11, 34, 57, 64, 86]
[3, 31, 46, 70, 99]
[16, 36, 43, 75, 92]

Answer 3

How about this random version one?

sample_result = []
arr = (1..100).to_a
diff = 15
result_len = 5
1.upto(result_len) {
    sample = arr.sample
    sample_result << sample
    (sample-diff..sample+diff).each do 
        |i| arr.delete(i)
    end
}
p sample_result.sort

Answer 4

Here's another way to approach this.

The smallest numbers allowed are:

a = Array.new(5) { |i| i * 3 + 1 }
#=> [1, 4, 7, 10, 13]

We can increment these numbers (or this group of numbers) 100 - 13 = 87 times until we hit the end:

87.times { a[0..-1] = a[0..-1].map(&:next) }
a #=> [88, 91, 94, 97, 100]

These are the largest numbers allowed.

Instead of incrementing all elements, we can pick a random element each time and increment that one (and it's right neighbors):

def spread(size, count, step)
  arr = Array.new(count) { |i| i * step + 1 }
  (size - arr.last).times do
    i = rand(0..arr.size)
    arr[i..-1] = arr[i..-1].map(&:next)
  end
  arr
end

5.times do
  p spread(100, 5, 3)
end

Output:

[21, 42, 56, 73, 86]
[6, 21, 45, 61, 81]
[20, 33, 48, 63, 81]
[12, 38, 55, 75, 90]
[11, 29, 50, 71, 86]
[26, 44, 64, 79, 95]

Unfortunately we have to loop several times to generate the final values. This is not only slow, but also results in a non-uniform distribution:

It would be better to determine 6 random offsets that sum to 87 and move the elements accordingly. Why 6? Because the offsets are the distances between our 5 numbers, i.e.:

       n1       n2                 n3     n4           n5            
|<-o1->|<--o2-->|<-------o3------->|<-o4->|<----o5---->|<----o6---->|
0                                                                  max

This helper method returns such offsets: (stolen from here)

def offsets(size, count)
  offsets = Array.new(count) { rand(0..size) }.sort
  [0, *offsets, size].each_cons(2).map { |a, b| b - a }
end

o = offsets(87, 5) #=> [3, 0, 15, 4, 64, 1]
o.inject(:+)       #=> 87

We can add the offsets to our initial number array:

def spread(size, count, step)
  arr = Array.new(count) { |i| i * step }
  offsets(size - arr.last, count).each_with_index do |offset, index|
    arr[index..-1] = arr[index..-1].map { |i| i + offset }
  end
  arr
end

5.times do
  p spread(99, 5, 3)
end

Output:

[1, 14, 48, 60, 94]
[12, 46, 54, 67, 72]
[8, 14, 35, 40, 45]
[27, 30, 51, 81, 94]
[63, 79, 86, 90, 96]

As expected, this results in a random distribution:

That looks better. Note that these results are zero based.

We can even remove the initial array and calculate the final values from the offsets. Starting with the first offset, we just have to add each following offset plus 3:

def spread(size, count, step)
  offs = offsets(size - (count - 1) * step, count)
  (1...offs.size).each { |i| offs[i] += offs[i-1] + step }
  offs[0, count]
end