CODEWITHSUNDEEP
scalarandom
Mobde
Mobde

Reputation: 11

Make a set of random Integers Scala

Is there a way in Scala to have a set of Ints be random without duplicates?

For example, I have set of Ints currently set to zero by default; a,b,c,d,e. And I want to assign a random int to each one from 1-100 while never assigning the same number to any of the variables. Thanks.

Upvotes: 1

Views: 848

Answers (2)

Aivean
Aivean

Reputation: 10882

I can see two ways how this can be done.

First is the simplest one. If the range (1-100) is small enough, you can just generate every value in this range, shuffle them and take first m:

import scala.util.Random

Random.shuffle(0 until 100 toList).take(4)

result:

res0: List[Int] = List(54, 11, 35, 15)

But if range is large, this won't be very efficient (as range must be materialized in the memory). So in the case when the number of picked values (m) is much smaller than the range (n), it's more efficient to generate random values until you pick one that wasn't used before.

Here is how:

import scala.util.Random

def distinctRandomMOutOfN(m:Int, n:Int):Set[Int] = {
  require(m <= n)
  Stream.continually(Random.nextInt(n)).scanLeft(Set[Int]()) {
    (accum, el) => accum + el
  }.dropWhile(_.size < m).head
}

distinctRandomMOutOfN(4, 100)

result:

res1: Set[Int] = Set(99, 28, 82, 87)

The downside of the second approach is that if m is close to n it takes average time close to O(m²) to compute.

UPD.

So if you want a general solution that will work efficiently in any case you may use hybrid variant. Use the first approach if m is at the same order of magnitude as n (i.e. m * 2 >= n) and second variant otherwise. This implementation will use O(m) memory and will have an average running time of O(m).

Upvotes: 2

jwvh
jwvh

Reputation: 51271

You can be confident that there are no duplicates if you simply shuffle all the possible elements and then take what you need.

import scala.util.Random

Random.shuffle(1 to 100).take(5)  // res0: Vector(74, 82, 68, 24, 15)

Upvotes: 1

Related Questions