Picking a Random Element from a Set

Picking a random element from a set

int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}

random.choice from set? python

Note (Oct. 2020): as of v3.9, Python has officially deprecated random.sample() working on sets, with the official guidance being to explicitly convert the set to a list or tuple before passing it in, though this doesn't solve the efficiency problems.

---

>>> random.sample(set('abcdefghijklmnopqrstuvwxyz'), 1)
['f']

Documentation: https://docs.python.org/3/library/random.html#random.sample

Note that choosing random elements from a set is extremely inefficient no matter how you do it - it takes time proportional to the size of the set, or worse if the set's underlying hash table is sparse due to removed elements.

Instead, you should probably use a different data structure that supports this operation efficiently.

Choose a random element from a set in O(1) time

I think it is impossible to get a random element from a hashtable (how a set is implemented) because it does not support random access. random.choice needs random access for this reason. You have a good alternative in set.pop, but it doesn't appear to be uniform (see https://github.com/python/cpython/blob/master/Objects/setobject.c#L616).

As long as it's not performance critical in a tight loop, converting to a list should be fine. However, if it does matter a lot, maybe you can consider using a different data structure in the first place.

Randomly selecting elements from a set in Python

Use random.sample:

import random
random.sample(s, k)

How to select a random element in std::set?

You could use the std::advance method.

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);
  auto r = rand() % s.size(); // not _really_ random
  auto n = *select_random(s, r);
}

Where

template<typename S>
auto select_random(const S &s, size_t n) {
  auto it = std::begin(s);
  // 'advance' the iterator n times
  std::advance(it,n);
  return it;
}

How can I randomly select an item from a list?

Use random.choice():

import random

foo = ['a', 'b', 'c', 'd', 'e']
print(random.choice(foo))

For cryptographically secure random choices (e.g., for generating a passphrase from a wordlist), use secrets.choice():

import secrets

foo = ['battery', 'correct', 'horse', 'staple']
print(secrets.choice(foo))

secrets is new in Python 3.6. On older versions of Python you can use the random.SystemRandom class:

import random

secure_random = random.SystemRandom()
print(secure_random.choice(foo))

Get Random Element from Collection

The most efficient it to only iterate as far as you need.

public static <T> T random(Collection<T> coll) {
    int num = (int) (Math.random() * coll.size());
    for(T t: coll) if (--num < 0) return t;
    throw new AssertionError();
}

Is it possible to find a random element in a Set in Constant time?

Yes it is possible to build a set-like data structure that supports O(1) getRandomElement operation. You are right about storing elements in an array. The problem of removing elements is not too difficult.

The secret is to compress the array once the number of holes is too large (say, more than half of the size of the array). This way the amortised deletion time is still O(1).

When performing getRandomElement(), just repeat until you hit an actual element. The mean number of repetitions is no more than 2, because the array is always at least half-full, so you still have your O(1) average time for getRandomElement().

Edit: perhaps a simpler method of deleting elements would be to move the last element to the vacated place.

How to get a random element from a Set in Scala

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

---

Related Topics