CODEWITHSUNDEEP
ruby
JayX
JayX

Reputation: 1784

How do I generate a random number within a non-contiguous range using Ruby?

For example suppose I have the following ranges

5031..5032 6248..6249

How do I generate a random number within these two ranges?

Upvotes: 3

Views: 871

Answers (6)

the Tin Man
the Tin Man

Reputation: 160551

This is what I came up with:

require 'benchmark'

class RangeRandom
  def initialize(ranges=[])

    # sanity checks need to go here for things like:
    #   backward/inverted ranges: (0..-1)
    #   range overlaps: (0..2 & 1..3)
    #     could combine ranges, or raise an exception
    #
    # Restrict to ranges that pass ".inclusive?"?

    # the end value is informative only
    @prepped_ranges = ranges.map{ |r| [ r.begin, r.end - r.begin, r.end ] }
  end

  def rand
    range = @prepped_ranges[ Kernel::rand( @prepped_ranges.size ) ]
    range[0] + Kernel::rand( range[1] )
  end
end

Some tests:

range_random = RangeRandom.new([0..10, 90..100])
5.times do
  puts range_random.rand
end
puts

# >> 94
# >> 97
# >> 92
# >> 92
# >> 8

n = 500_000
Benchmark.bm(7) do |x|
  x.report('rand1:') { n.times do ; r = RangeRandom.new([ 0..1             ]); r.rand; end }
  x.report('rand2:') { n.times do ; r = RangeRandom.new([ 0..1_000_000     ]); r.rand; end }
  x.report('rand3:') { n.times do ; r = RangeRandom.new([ 0..1_000_000_000 ]); r.rand; end }

  x.report('rand4:') { n.times do ; r = RangeRandom.new([ 0..1 ]); r.rand; end }
  x.report('rand5:') { n.times do ; r = RangeRandom.new([ 0..1, 2..3, 4..5, 6..7 ]); r.rand; end }

  x.report('rand6:') { r = RangeRandom.new([ 0..1             ]) ; n.times do ; r.rand; end }
  x.report('rand7:') { r = RangeRandom.new([ 0..1_000_000_000 ]) ; n.times do ; r.rand; end }
end

Overall run times for 500,000 iterations:

# >>              user     system      total        real
# >> rand1:   2.220000   0.000000   2.220000 (  2.224894)
# >> rand2:   2.250000   0.010000   2.260000 (  2.254730)
# >> rand3:   2.250000   0.000000   2.250000 (  2.247406)

Times for initializing multiple ranges for 500,000 iterations:

# >> rand4:   2.220000   0.000000   2.220000 (  2.222983)
# >> rand5:   4.340000   0.000000   4.340000 (  4.337312)

Times for a single initialization, then a small range vs. big range for 500,000 iterations:

# >> rand6:   0.560000   0.000000   0.560000 (  0.559673)
# >> rand7:   0.580000   0.000000   0.580000 (  0.584331)

Times increase a little when using big ranges but that might be variations due to system activity. Initializing multiple ranges in the array has a greater effect which is what I expected.

Upvotes: 1

DigitalRoss
DigitalRoss

Reputation: 146043

The simple way:

(r1.to_a + r2.to_a).choice

A faster and much more memory-efficient general solution would involve computing the total range size, generating a random number, and then normalizing the number to the range that it falls in.

Update: Ok, got it. This solution works with an arbitrary number of Ranges and does not generate giant arrays or iterate through the Ranges themselves. (It iterates twice over an array of Ranges, not arrays of Range elements.)

def rangerand *r
  r.inject(rand(
      r.inject(0) do |accum, rng|
        accum + rng.last - rng.first + 1
      end
    )) do |accum, rng|
      rngsize = rng.last - rng.first + 1
      return rng.first + accum if accum < rngsize
      accum - rngsize
    end
  # raise 'this "cannot happen"'
end

puts rangerand 1..3, 999..1001, 10_200..10_205

Heh, I've never used two #injects in the same expression before.

Upvotes: 5

tokland
tokland

Reputation: 67850

I wrote this code and looking now at Nikita's answer I think it's more or less his idea (I use r.end/r.begin because Ruby ranges have no pre-calculated length attribute)

ranges = [1..10, 21..40, 81..120]

counts = ranges.map { |r| r.end - r.begin + (r.exclude_end? ? 0 : 1) }
random = rand(counts.inject(&:+))    
idx, remainder = counts.inject([0, random]) do |(idx, remainder), count|
  if remainder < count
    [idx, remainder] # break here if you care more for efficiency than for functional purity
  else
    [idx+1, remainder - count]
  end
end
p ranges[idx].begin + remainder

Of course if I had ranges of reasonable length, I'd simply use the other solutions already discussed.

Upvotes: 3

Marcin Urbanski
Marcin Urbanski

Reputation: 2493

For wide ranges range.to_a is not a very good solution. You can create unnecessarily many big arrays. Fastest solution can look like this:

ruby-1.9.2-head > from, to = 1, 50000000
 => [1, 50000000] 
ruby-1.9.2-head > from + rand(to-from+1) 
 => 20698596 
ruby-1.9.2-head > from + rand(to-from+1) 
 => 15143263 
ruby-1.9.2-head > from + rand(to-from+1) 
 => 18469491

Similar solution for Ranges is however almost as slow as range.to_a:

ruby-1.9.2-head > range1 = 1..5000000
 => 50..50000 
ruby-1.9.2-head > range1.begin + rand(range1.count)   # TAKES ABOUT 1 SECOND!
 => 1788170

Upvotes: 0

Ryan Bigg
Ryan Bigg

Reputation: 107718

Add the ranges to an array and flatten it to get a series of numbers, then call rand to find a particular element of this array.

range_1 = 1..10
range_2 = 2..30

range_array = [range_1.to_a, range_2.to_a].flatten
range_array[rand(range_array.length)]

Upvotes: 1

Nikita Rybak
Nikita Rybak

Reputation: 68006

For arbitrary number of ranges

  1. Count number of possible values as total.
  2. Generate random number rnd between 0 and total - 1.
  3. Iterate through list of ranges, subtracting range size from rnd until possible (until rnd is non-negative).
  4. When can't subtract more, just get rnd-th number in the current range.

Upvotes: 4

Related Questions