How to get a random element from a Set in Scala

Question

For any given set, for instance,

val fruits = Set("apple", "grape", "pear", "banana")

how to get a random element from fruits ?

Many Thanks.

Solution 1

convert into Vector and get random element from it

scala> val fruits = Set("apple", "grape", "pear", "banana")
fruits: scala.collection.immutable.Set[String] = Set(apple, grape, pear, banana)

scala> import scala.util.Random
import scala.util.Random

scala> val rnd=new Random
rnd: scala.util.Random = scala.util.Random@31a9253

scala> fruits.toVector(rnd.nextInt(fruits.size))
res8: String = apple

Solution 2

So, every answer posted before has complexity O(n) in terms of space, since they create a copy a whole collection in some way. Here is a solution without any additional copying (therefore it is "constant space"):

def random[T](s: Set[T]): T = {
  val n = util.Random.nextInt(s.size)
  s.iterator.drop(n).next
}

Solution 3

Drawing inspiration from the other answers to this question, I've come up with:

private def randomItem[T](items: Traversable[T]): Option[T] = {
  val i = Random.nextInt(items.size)
  items.view(i, i + 1).headOption
}

This doesn't copy anything, doesn't fail if the Set (or other type of Traversable) is empty, and it's clear at a glance what it does. If you're certain that the Set is not empty, you could use .head instead of headOption, returning a T.

Solution 4

You can directly access an element of a Set with slice. I used this when I was working with a set that was changing in size, so converting it to a Vector every time seemed like overkill.

val roll = new Random ()

val n = roll nextInt (fruits size)
fruits slice (n, n + 1) last

Solution 5

Solution1

Random way ( import scala.util.Random )

scala>  fruits.toList(Random.nextInt(fruits.size))
res0: java.lang.String = banana

Solution2

Math way (no imports)

scala> fruits.toList((math.random*fruits.size).toInt)
res1: String = banana

View more solutions

Comments

[Ashalynd]

Yep, Set should be converted to container that supports accessing elements by sequential number. Vector is quicker than List.

[Kigyo]

Indexing is O(n) on List. Why not use Array or Vector?

[Govind Singh]

@dividebyzero previously it was set

[justinhj]

This is a better answer for the reason you put forward. It could be done in a one liner like this: val s = Set(1,2,3); s.drop(random.nextInt(s.size).head

[Rok Kralj]

@justinhj: Nope, your solution is O(n) space again, since drop on Set causes a set with the remaining elements to be created. You have to use iterators, because they are non-strict.

[durai]

Good solution. Its worth pointing out that if the set is empty it.next will throw.

[Jus12]

@AntonyPerkov which makes sense because ... what does it mean to sample from an empty set?

[Brian McCutchon]

This is still O(n) time, though.

[kkessell]

Yes, I also look for a O(1) time and O(1) space version

[Rok Kralj]

You will have to create your own Set implementation for that. and the time will probably be O(log n) if you want to have other operations efficient.

[Boris]

Chained List is not a good option to pick one element at random. Chose array or vector instead

[Tim Barrass]

Can't scala.util.Random.nextInt occasionally return negative numbers?

[László van den Hoek]

@TimBarrass nextInt() will return a negative number half of the time, but nextInt(n: Int), which is used here, starts at 0 and ends at n (exclusive): scala-lang.org/api/current/scala/util/…

[Abhijit Sarkar]

Or convert to IndexedSeq, and code to interfaces.