How do I generate a list of n unique random numbers in Ruby?

Question

This is what I have so far:

myArray.map!{ rand(max) }

Obviously, however, sometimes the numbers in the list are not unique. How can I make sure my list only contains unique numbers without having to create a bigger list from which I then just pick the n unique numbers?

Edit:
I'd really like to see this done w/o loop - if at all possible.

Answer 1

This uses Set:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    loop do
        randoms << rand(max)
        return randoms.to_a if randoms.size >= n
    end
end

Answer 2

(0..50).to_a.sort{ rand() - 0.5 }[0..x] 

(0..50).to_a can be replaced with any array. 0 is "minvalue", 50 is "max value" x is "how many values i want out"

of course, its impossible for x to be permitted to be greater than max-min :)

In expansion of how this works

(0..5).to_a  ==> [0,1,2,3,4,5]
[0,1,2,3,4,5].sort{ -1 }  ==>  [0, 1, 2, 4, 3, 5]  # constant
[0,1,2,3,4,5].sort{  1 }  ==>  [5, 3, 0, 4, 2, 1]  # constant
[0,1,2,3,4,5].sort{ rand() - 0.5 }   ==>  [1, 5, 0, 3, 4, 2 ]  # random
[1, 5, 0, 3, 4, 2 ][ 0..2 ]   ==>  [1, 5, 0 ]

Footnotes:

It is worth mentioning that at the time this question was originally answered, September 2008, that Array#shuffle was either not available or not already known to me, hence the approximation in Array#sort

And there's a barrage of suggested edits to this as a result.

So:

.sort{ rand() - 0.5 }

Can be better, and shorter expressed on modern ruby implementations using

.shuffle

Additionally,

[0..x]

Can be more obviously written with Array#take as:

.take(x)

Thus, the easiest way to produce a sequence of random numbers on a modern ruby is:

(0..50).to_a.shuffle.take(x)

Answer 3

Just to give you an idea about speed, I ran four versions of this:

1. Using Sets, like Ryan's suggestion.
2. Using an Array slightly larger than necessary, then doing uniq! at the end.
3. Using a Hash, like Kyle suggested.
4. Creating an Array of the required size, then sorting it randomly, like Kent's suggestion (but without the extraneous "- 0.5", which does nothing).

They're all fast at small scales, so I had them each create a list of 1,000,000 numbers. Here are the times, in seconds:

1. Sets: 628
2. Array + uniq: 629
3. Hash: 645
4. fixed Array + sort: 8

And no, that last one is not a typo. So if you care about speed, and it's OK for the numbers to be integers from 0 to whatever, then my exact code was:

a = (0...1000000).sort_by{rand}

Answer 4

Ruby 1.9 offers the Array#sample method which returns an element, or elements randomly selected from an Array. The results of #sample won't include the same Array element twice.

(1..999).to_a.sample 5 # => [389, 30, 326, 946, 746]

When compared to the to_a.sort_by approach, the sample method appears to be significantly faster. In a simple scenario I compared sort_by to sample, and got the following results.

require 'benchmark'
range = 0...1000000
how_many = 5

Benchmark.realtime do
  range.to_a.sample(how_many)
end
=> 0.081083

Benchmark.realtime do
  (range).sort_by{rand}[0...how_many]
end
=> 2.907445

Answer 5

Yes, it's possible to do this without a loop and without keeping track of which numbers have been chosen. It's called a Linear Feedback Shift Register: Create Random Number Sequence with No Repeats

Answer 6

How about a play on this? Unique random numbers without needing to use Set or Hash.

x = 0
(1..100).map{|iter| x += rand(100)}.shuffle

Answer 7

You could use a hash to track the random numbers you've used so far:

seen = {}
max = 100
(1..10).map { |n|
  x = rand(max)
  while (seen[x]) 
    x = rand(max)
  end
  x
}

Answer 8

Rather than add the items to a list/array, add them to a Set.

Answer 9

If you have a finite list of possible random numbers (i.e. 1 to 100), then Kent's solution is good.

Otherwise there is no other good way to do it without looping. The problem is you MUST do a loop if you get a duplicate. My solution should be efficient and the looping should not be too much more than the size of your array (i.e. if you want 20 unique random numbers, it might take 25 iterations on average.) Though the number of iterations gets worse the more numbers you need and the smaller max is. Here is my above code modified to show how many iterations are needed for the given input:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    i = 0
    loop do
        randoms << rand(max)
        break if randoms.size > n
        i += 1
    end
    puts "Took #{i} iterations for #{n} random numbers to a max of #{max}"
    return randoms.to_a
end

I could write this code to LOOK more like Array.map if you want :)

Answer 10

Based on Kent Fredric's solution above, this is what I ended up using:

def n_unique_rand(number_to_generate, rand_upper_limit)
  return (0..rand_upper_limit - 1).sort_by{rand}[0..number_to_generate - 1]
end

Thanks Kent.

Answer 11

No loops with this method

Array.new(size) { rand(max) }

require 'benchmark'
max = 1000000
size = 5
Benchmark.realtime do
  Array.new(size) { rand(max) }
end

=> 1.9114e-05 

Answer 12

Here is one solution:

Suppose you want these random numbers to be between r_min and r_max. For each element in your list, generate a random number r, and make list[i]=list[i-1]+r. This would give you random numbers which are monotonically increasing, guaranteeing uniqueness provided that

• r+list[i-1] does not over flow
• r > 0

For the first element, you would use r_min instead of list[i-1]. Once you are done, you can shuffle the list so the elements are not so obviously in order.

The only problem with this method is when you go over r_max and still have more elements to generate. In this case, you can reset r_min and r_max to 2 adjacent element you have already computed, and simply repeat the process. This effectively runs the same algorithm over an interval where there are no numbers already used. You can keep doing this until you have the list populated.

Answer 13

As far as it is nice to know in advance the maxium value, you can do this way:

class NoLoopRand
  def initialize(max)
    @deck = (0..max).to_a
  end

  def getrnd
    return @deck.delete_at(rand(@deck.length - 1))
  end
end

and you can obtain random data in this way:

aRndNum = NoLoopRand.new(10)
puts aRndNum.getrnd

you'll obtain nil when all the values will be exausted from the deck.

Answer 14

Method 1

Using Kent's approach, it is possible to generate an array of arbitrary length keeping all values in a limited range:

# Generates a random array of length n.
#
# @param n     length of the desired array
# @param lower minimum number in the array
# @param upper maximum number in the array
def ary_rand(n, lower, upper)
    values_set = (lower..upper).to_a
    repetition = n/(upper-lower+1) + 1
    (values_set*repetition).sample n
end

Method 2

Another, possibly more efficient, method modified from same Kent's another answer:

def ary_rand2(n, lower, upper)
    v = (lower..upper).to_a
    (0...n).map{ v[rand(v.length)] }
end

Output

puts (ary_rand 5, 0, 9).to_s # [0, 8, 2, 5, 6] expected
puts (ary_rand 5, 0, 9).to_s # [7, 8, 2, 4, 3] different result for same params
puts (ary_rand 5, 0, 1).to_s # [0, 0, 1, 0, 1] repeated values from limited range
puts (ary_rand 5, 9, 0).to_s # []              no such range :)