# Picking a random element from a set

How do I pick a random element from a set? I’m particularly interested in picking a random element from a HashSet or a LinkedHashSet, in Java. Solutions for other languages are also welcome.

Picking random element from array [duplicate]

Possible Duplicate: How do I pick randomly from an array? What is the appropriate way to ensure that a non-existent item isn’t chosen? icons = %w[asterisk star arrow] random = rand(icons.length) o

Picking a random element from a Multidimensional Array

Please Does anyone know how to pick a random element from an array? I know how to implement on normal Variables Random rnd = new Random(); int no = rnd.Next(30); Console.WriteLine(no); but i need to

Picking a random array element from an associative array

How would I pick a random array element from an associative array with regards to array length ? For example: actors[name]=firstname movielist[title]=[director,artwork,actors] If I wanted to pull out

Picking random element from an array in Ruby ONCE ONLY

I know I can pick a random element out of an array with the sample method but this leaves the possibility of an element being picked more than once. I could shuffle the array first and then go from fi

Picking a random array element from an array [duplicate]

Possible Duplicate: How can I return a random value from an array? Getting random value from an array If you have an array of: days = [Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,

Picking out a random element from an organised ArrayList

So the idea here is that I have an ArrayList with a set of words, I want to sort the list so that it only includes entries with even numbered indecies and then picks out an entry at random. I gave thi

Pick random element from set with non-uniform distribution?

I would like to have a set and have its elements have probabilities associated with them, so when I pick an element at random from the set, the distribution follows the probabilities associated with t

Random element from unordered_set in O(1)

I’ve seen people mention that a random element can be grabbed from an unordered_set in O(1) time. I attempted to do so with this: std::unordered_set<TestObject*> test_set; //fill with data size_

Picking 2 random elements from array

What is the most efficient way to select 2 unique random elements from an array (ie, make sure the same element is not selected twice). I have so far: var elem1; var elem2; elem1 = elemList[Math.ceil(

How to get a random element from a Set in Scala

For any given set, for instance, val fruits = Set(apple, grape, pear, banana) how to get a random element from fruits ? Many Thanks.

Since you said “Solutions for other languages are also welcome”, here’s the version for Python:

```>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
```

In Java:

```Set<Integer> set = new LinkedHashSet<Integer>(3);

Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
System.out.println(setArray[rand.nextInt(set.size())]);
}
```
```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 = i + 1;
}
```

Can’t you just get the size/length of the set/array, generate a random number between 0 and the size/length, then call the element whose index matches that number? HashSet has a .size() method, I’m pretty sure.

In psuedocode –

```function randFromSet(target){
var targetLength:uint = target.length()
var randomIndex:uint = random(0,targetLength);
return target[randomIndex];
}
```

PHP, assuming “set” is an array:

```\$foo = array("alpha", "bravo", "charlie");
\$index = array_rand(\$foo);
\$val = \$foo[\$index];
```

The Mersenne Twister functions are better but there’s no MT equivalent of array_rand in PHP.

PHP, using MT:

```\$items_array = array("alpha", "bravo", "charlie");
\$last_pos = count(\$items_array) - 1;
\$random_pos = mt_rand(0, \$last_pos);
\$random_item = \$items_array[\$random_pos];
```

Javascript solution ðŸ˜‰

```function choose (set) {
return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);
```

Or alternatively:

```Array.prototype.choose = function () {
return this[Math.floor(Math.random() * this.length)];
};

[1, 2, 3, 4].choose();
```

A somewhat related Did You Know:

There are useful methods in java.util.Collections for shuffling whole collections:

```/**
* Randomly permutes the specified list using a default source of
* randomness.  All permutations occur with approximately equal
* likelihood.<p>
*
* The hedge "approximately" is used in the foregoing description because
* default source of randomness is only approximately an unbiased source
* of independently chosen bits. If it were a perfect source of randomly
* chosen bits, then the algorithm would choose permutations with perfect
* uniformity.<p>
*
* This implementation traverses the list backwards, from the last element
* up to the second, repeatedly swapping a randomly selected element into
* the "current position".  Elements are randomly selected from the
* portion of the list that runs from the first element to the current
* position, inclusive.<p>
*
* This method runs in linear time.  If the specified list does not
* implement the {@link RandomAccess} interface and is large, this
* implementation dumps the specified list into an array before shuffling
* it, and dumps the shuffled array back into the list.  This avoids the
* quadratic behavior that would result from shuffling a "sequential
* access" list in place.
*
* @param  list the list to be shuffled.
* @throws UnsupportedOperationException if the specified list or
*         its list-iterator does not support the <tt>set</tt> operation.
*/
public static void shuffle(List<?> list) {
...
}
```

and also

```public static void shuffle(List<?> list, Random rnd) {
...
}
```

Perl 5

```@hash_keys = (keys %hash);
\$rand = int(rand(@hash_keys));
print \$hash{\$hash_keys[\$rand]};
```

Here is one way to do it.

Icon has a set type and a random-element operator, unary “?”, so the expression

```? set( [1, 2, 3, 4, 5] )
```

will produce a random number between 1 and 5.

The random seed is initialized to 0 when a program is run, so to produce different results on each run use randomize()

In C#

```        Random random = new Random((int)DateTime.Now.Ticks);

OrderedDictionary od = new OrderedDictionary();

int randomIndex = random.Next(od.Count);

Console.WriteLine(od[randomIndex]);

// Can access via index or key value:
Console.WriteLine(od[1]);
Console.WriteLine(od["def"]);
```

In lisp

```(defun pick-random (set)
(nth (random (length set)) set))
```

If you want to do it in Java, you should consider copying the elements into some kind of random-access collection (such as an ArrayList). Because, unless your set is small, accessing the selected element will be expensive (O(n) instead of O(1)). [ed: list copy is also O(n)]

Alternatively, you could look for another Set implementation that more closely matches your requirements. The ListOrderedSet from Commons Collections looks promising.

Clojure solution:

```(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
```

Unfortunately, this cannot be done efficiently (better than O(n)) in any standard set containers I know of.

This is odd, since it is very easy to add a randomized pick function to hash sets as well as binary sets. In a not to sparse hash set, you can try random entries, until you get a hit. For a binary tree, you can choose randomly between the left or right subtree, with a maximum of O(log2) steps. I’ve implemented a demo of the later below:

```import random

class Node:
def __init__(self, object):
self.object = object
self.value = hash(object)
self.size = 1
self.a = self.b = None

class RandomSet:
def __init__(self):
self.top = None

""" Add any hashable object to the set.
Notice: In this simple implementation you shouldn't add two
identical items. """
new = Node(object)
if not self.top: self.top = new
top.size += 1
if new.value < top.value:
if not top.a: top.a = new
else:
if not top.b: top.b = new

def pickRandom(self):
""" Pick a random item in O(log2) time.
Does a maximum of O(log2) calls to random as well. """
return self._recursivePickRandom(self.top)
def _recursivePickRandom(self, top):
r = random.randrange(top.size)
elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
return self._recursivePickRandom(top.b)

if __name__ == '__main__':
s = RandomSet()
for i in [5,3,7,1,4,6,9,2,8,0]:

dists = [0]*10
for i in xrange(10000):
dists[s.pickRandom()] += 1
print dists
```

I got [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] as output, so the distribution seams good.

I’ve struggled with the same problem for myself, and I haven’t yet decided weather the performance gain of this more efficient pick is worth the overhead of using a python based collection. I could of course refine it and translate it to C, but that is too much work for me today ðŸ™‚

C++. This should be reasonably quick, as it doesn’t require iterating over the whole set, or sorting it. This should work out of the box with most modern compilers, assuming they support tr1. If not, you may need to use Boost.

The Boost docs are helpful here to explain this, even if you don’t use Boost.

The trick is to make use of the fact that the data has been divided into buckets, and to quickly identify a randomly chosen bucket (with the appropriate probability).

```//#include <boost/unordered_set.hpp>
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;

int main() {
unordered_set<int> u;
for (int i=0; i<40; i++) {
u.insert(i);
cout << ' ' << i;
}
cout << endl;
cout << "Number of buckets: " << u.bucket_count() << endl;

for(size_t b=0; b<u.bucket_count(); b++)
cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;

for(size_t i=0; i<20; i++) {
size_t x = rand() % u.size();
cout << "we'll quickly get the " << x << "th item in the unordered set. ";
size_t b;
for(b=0; b<u.bucket_count(); b++) {
if(x < u.bucket_size(b)) {
break;
} else
x -= u.bucket_size(b);
}
cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
unordered_set<int>::const_local_iterator l = u.begin(b);
while(x>0) {
l++;
assert(l!=u.end(b));
x--;
}
cout << "random item is " << *l << ". ";
cout << endl;
}
}
```

```static Random random = new Random(System.currentTimeMillis());
public static <T> T randomChoice(T[] choices)
{
int index = random.nextInt(choices.length);
return choices[index];
}
```

Fast solution for Java using an ArrayList and a HashMap: [element -> index].

Motivation: I needed a set of items with RandomAccess properties, especially to pick a random item from the set (see pollRandom method). Random navigation in a binary tree is not accurate: trees are not perfectly balanced, which would not lead to a uniform distribution.

```public class RandomSet<E> extends AbstractSet<E> {

List<E> dta = new ArrayList<E>();
Map<E, Integer> idx = new HashMap<E, Integer>();

public RandomSet() {
}

public RandomSet(Collection<E> items) {
for (E item : items) {
idx.put(item, dta.size());
}
}

@Override
if (idx.containsKey(item)) {
return false;
}
idx.put(item, dta.size());
return true;
}

/**
* Override element at position <code>id</code> with last element.
* @param id
*/
public E removeAt(int id) {
if (id >= dta.size()) {
return null;
}
E res = dta.get(id);
idx.remove(res);
E last = dta.remove(dta.size() - 1);
// skip filling the hole if last is removed
if (id < dta.size()) {
idx.put(last, id);
dta.set(id, last);
}
return res;
}

@Override
public boolean remove(Object item) {
@SuppressWarnings(value = "element-type-mismatch")
Integer id = idx.get(item);
if (id == null) {
return false;
}
removeAt(id);
return true;
}

public E get(int i) {
return dta.get(i);
}

public E pollRandom(Random rnd) {
if (dta.isEmpty()) {
return null;
}
int id = rnd.nextInt(dta.size());
return removeAt(id);
}

@Override
public int size() {
return dta.size();
}

@Override
public Iterator<E> iterator() {
return dta.iterator();
}
}
```

In Mathematica:

```a = {1, 2, 3, 4, 5}

a[[ âŒˆ Length[a] Random[] âŒ‰ ]]
```

```RandomChoice[a]
```

This received a down-vote, perhaps because it lacks explanation, so here one is:

Random[] generates a pseudorandom float between 0 and 1. This is multiplied by the length of the list and then the ceiling function is used to round up to the next integer. This index is then extracted from a.

Since hash table functionality is frequently done with rules in Mathematica, and rules are stored in lists, one might use:

```a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};
```
```List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
```

```public static <A> A getRandomElement(Collection<A> c, Random r) {
return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
```

For fun I wrote a RandomHashSet based on rejection sampling. It’s a bit hacky, since HashMap doesn’t let us access it’s table directly, but it should work just fine.

It doesn’t use any extra memory, and lookup time is O(1) amortized. (Because java HashTable is dense).

```class RandomHashSet<V> extends AbstractSet<V> {
private Map<Object,V> map = new HashMap<>();
return map.put(new WrapKey<V>(v),v) == null;
}
@Override
public Iterator<V> iterator() {
return new Iterator<V>() {
RandKey key = new RandKey();
@Override public boolean hasNext() {
return true;
}
@Override public V next() {
while (true) {
key.next();
V v = map.get(key);
if (v != null)
return v;
}
}
@Override public void remove() {
throw new NotImplementedException();
}
};
}
@Override
public int size() {
return map.size();
}
static class WrapKey<V> {
private V v;
WrapKey(V v) {
this.v = v;
}
@Override public int hashCode() {
return v.hashCode();
}
@Override public boolean equals(Object o) {
if (o instanceof RandKey)
return true;
return v.equals(o);
}
}
static class RandKey {
private Random rand = new Random();
int key = rand.nextInt();
public void next() {
key = rand.nextInt();
}
@Override public int hashCode() {
return key;
}
@Override public boolean equals(Object o) {
return true;
}
}
}
```

This is faster than the for-each loop in the accepted answer:

```int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
```

The for-each construct calls Iterator.hasNext() on every loop, but since index < set.size(), that check is unnecessary overhead. I saw a 10-20% boost in speed, but YMMV. (Also, this compiles without having to add an extra return statement.)

Note that this code (and most other answers) can be applied to any Collection, not just Set. In generic method form:

```public static <E> E choice(Collection<? extends E> coll, Random rand) {
int index = rand.nextInt(coll.size());
if (coll instanceof List) { // optimization
return ((List<? extends E>) coll).get(index);
} else {
Iterator<? extends E> iter = coll.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
}
}
```

you can also transfer the set to array use array it will probably work on small scale i see the for loop in the most voted answer is O(n) anyway

```Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];
```

This is identical to accepted answer (Khoth), but with the unnecessary size and i variables removed.

```    int random = new Random().nextInt(myhashSet.size());
for(Object obj : myhashSet) {
if (random-- == 0) {
return obj;
}
}
```

Solution above speak in terms of latency but doesn’t guarantee equal probability of each index being selected.
If that needs to be considered, try reservoir sampling. http://en.wikipedia.org/wiki/Reservoir_sampling.
Collections.shuffle() (as suggested by few) uses one such algorithm.

If you really just want to pick “any” object from the Set, without any guarantees on the randomness, the easiest is taking the first returned by the iterator.

```    Set<Integer> s = ...
Iterator<Integer> it = s.iterator();
if(it.hasNext()){
Integer i = it.next();
// i is a "random" object from set
}
```

The easiest with Java 8 is:

```outbound.stream().skip(n % outbound.size()).findFirst().get()
```

where n is a random integer. Of course it is of less performance than that with the for(elem: Col)

A generic solution using Khoth’s answer as a starting point.

```/**
* @param set a Set in which to look for a random element
* @param <T> generic type of the Set elements
* @return a random element in the Set or null if the set is empty
*/
public <T> T randomElement(Set<T> set) {
int size = set.size();
int item = random.nextInt(size);
int i = 0;
for (T obj : set) {
if (i == item) {
return obj;
}
i++;
}
return null;
}
```

Ok so here’s where i needed SOMETHING close to you did.

See problem: http://codeforces.com/contest/534/problem/D (Don’t need to understand)

Here, I had to create a Map which stored an integer as a key and needed a Set/List to store a list of values.

Here I tried using ArrayList but it was slow and gave me ‘Time Limit Exceeded’.

Now the important part: If the order of elements is not important and you just want to remove a RANDOM element every time, why not use a STACK? Just keep adding and popping when necessary. Worked for me and i got the code Accepted ðŸ˜€

Here’s the one with the ArrayList which did not get AC: http://codeforces.com/contest/534/submission/10687311

If set size is not large then by using Arrays this can be done.

```int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
```

With Guava we can do a little better than Khoth’s answer:

```public static E random(Set<E> set) {
int index = random.nextInt(set.size();
if (set instanceof ImmutableSet) {
// ImmutableSet.asList() is O(1), as is .get() on the returned list
return set.asList().get(index);
}
return Iterables.get(set, index);
}
```