By Clue Less


2008-09-24 00:12:17 8 Comments

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.

30 comments

@Joshua Bone 2018-07-19 01:15:32

In Java 8:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

@RKumsher 2017-08-07 23:05:33

If you don't mind a 3rd party library, the Utils library has a IterableUtils that has a randomFrom(Iterable iterable) method that will take a Set and return a random element from it

Set<Object> set = new HashSet<>();
set.add(...);
...
Object random = IterableUtils.randomFrom(set);

It is in the Maven Central Repository at:

<dependency>
  <groupId>com.github.rkumsher</groupId>
  <artifactId>utils</artifactId>
  <version>1.3</version>
</dependency>

@Thomas Ahle 2009-12-27 00:13:39

Unfortunately, this cannot be done efficiently (better than O(n)) in any of the Standard Library set containers.

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

    def add(self, object):
        """ 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
        else: self._recursiveAdd(self.top, new)
    def _recursiveAdd(self, top, new):
        top.size += 1
        if new.value < top.value:
            if not top.a: top.a = new
            else: self._recursiveAdd(top.a, new)
        else:
            if not top.b: top.b = new
            else: self._recursiveAdd(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)
        if r == 0: return top.object
        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]:
        s.add(i)

    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 :)

@Willem Van Onsem 2012-12-13 01:55:12

A reason I think this is not implemented in a binary tree is that such a method wouldn't pick items uniformly. Since their are nodes without left/right children, a situation may occur where the left child contains more items than the right child (or vice versa), this would make picking an item at the right (or left) child, more probable.

@Thomas Ahle 2012-12-13 13:09:29

@CommuSoft: That's why I store the size of each subtree, so I can choose my probabilities based on those.

@Jason Hartley 2014-12-08 06:53:11

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;
        }
    }

Though doing away with the two aforementioned variables, the above solution still remains random because we are relying upon random (starting at a randomly selected index) to decrement itself toward 0 over each iteration.

@Salvador 2019-08-20 14:41:57

Third line could also be if (--random < 0) {, where random reaches -1.

@Khoth 2008-09-24 00:17:08

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++;
}

@daniel 2008-09-24 02:30:35

If myHashSet is large, then this will be a rather slow solution since on average, (n / 2) iterations will be needed to find the random object.

@David Nehme 2008-09-25 02:00:14

if your data is in a hash set, you need O(n) time. There's no way around it if you are just picking a single element and the data is stored in a HashSet.

@Aaron McDaid 2010-07-20 13:50:17

@David Nehme: This is a drawback in the specification of HashSet in Java. In C++, it's typical to be able to directly access the buckets that make up the hashset, which allows us to more efficiently select a random elements. If random elements are necessary in Java, it might be worthwhile to define a custom hash set that allows the user to look under the hood. See [boost's docs][1] for a little more in this. [1] boost.org/doc/libs/1_43_0/doc/html/unordered/buckets.html

@ykaganovich 2010-07-21 20:23:09

If the set is not mutated over multiple accesses, you can copy it into an array and then access O(1). Just use myHashSet.toArray()

@Viktor Dahl 2012-08-20 08:34:35

@AaronMcDaid Even then, you would have to take empty buckets into account.

@anton1980 2014-11-22 03:19:33

@ykaganovich wouldn't this make matters worse, since the set would have to be copied to a new array? docs.oracle.com/javase/7/docs/api/java/util/… "this method must allocate a new array even if this collection is backed by an array"

@ykaganovich 2014-11-24 00:33:14

@anton1980 See discussion under Dan Dyer's answer stackoverflow.com/a/129386/10026

@dimo414 2016-04-28 15:22:01

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);
}

@chickeninabiscuit 2008-09-24 00:43:03

A somewhat related Did You Know:

There are useful methods in java.util.Collections for shuffling whole collections: Collections.shuffle(List<?>) and Collections.shuffle(List<?> list, Random rnd).

@smci 2012-02-08 19:48:36

Awesome! This is not crossreferenced anywhere in the java doc! Like Python's random.shuffle()

@bourbaki4481472 2015-02-19 22:27:23

But this only works with Lists, i.e., structures that have a .get() function.

@Thomas 2015-02-28 20:57:26

@bourbaki4481472 is absolutely correct. This only works for those collections extending the List interface, not the Set interface discussed by the OP.

@BHARAT ARYA 2016-01-04 15:10:55

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];

@stivlo 2015-03-27 10:52:44

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;
}

@Nicu Marasoiu 2015-02-24 20:20:06

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)

@Philipp 2015-02-04 15:50:10

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
    }

@Menezes Sousa 2015-09-06 06:01:31

This will not be a random pick though. Imagine performing the same operation over the same set multiple times. I think the order will be the same.

@thepace 2014-12-08 07:03:09

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.

@Sean Van Gorder 2014-08-20 17:03:58

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) {
    if (coll.size() == 0) {
        return null; // or throw IAE, if you prefer
    }

    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();
    }
}

@sivi 2014-11-11 19:43:58

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)];

@Thomas Ahle 2013-12-22 14:05:55

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<>();
    public boolean add(V v) {
        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;
        }
    }
}

@momomo 2015-10-08 11:22:42

Exactly what I was thinking! Best answer!

@Thomas Ahle 2016-04-07 12:31:24

Actually, coming back to it, I guess this isn't quite uniform, if the hashmap has many collisions and we do many queries. That is because the java hashmap uses buckets/chaining and this code will always return the first element in the particular bucket. We're still uniform over the randomness of the hash function though.

@Daniel Lubarov 2012-12-18 21:06:08

How about just

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

@Ben Noland 2012-12-04 22:18:05

List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);

@Chris Bode 2013-03-11 01:28:36

This is abysmally inefficient. Your ArrayList constructor calls .toArray() on the supplied set. ToArray (in most if not all standard collection implementations) iterates over the entire collection, filling an array as it goes. Then you shuffle the list, which swaps each element with a random element. You'd be much better off simply iterating over the set to a random element.

@Rushikesh Garadade 2014-08-06 08:20:17

Short and sweet.......awesome

@Jorge Ferreira 2008-09-24 00:16:32

In Java:

Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(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())]);
}

@Clue Less 2008-09-24 01:34:38

Your answer works, but it's not very efficient because of the set.toArray( ) part.

@David Nehme 2008-09-25 01:57:25

you should move the toArray to outside the loop.

@Mr.Wizard 2011-04-15 23:14:41

In Mathematica:

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

a[[ ⌈ Length[a] Random[] ⌉ ]]

Or, in recent versions, simply:

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};

@fandrew 2011-04-14 20:06:48

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());
            dta.add(item);
        }
    }

    @Override
    public boolean add(E item) {
        if (idx.containsKey(item)) {
            return false;
        }
        idx.put(item, dta.size());
        dta.add(item);
        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();
    }
}

@Thomas Ahle 2013-12-21 22:03:10

Best solution in the thread. Kudos :)

@Johan Tidén 2015-05-05 16:42:30

Well that would work but the question was about the Set interface. This solution forces users to have concrete type references of the RandomSet.

@Kostas Chalkias 2015-12-18 07:17:33

I really like this solution, but it's not thread safe, inaccuracies between the Map and the List may occur, so I would add some synchronized blocks

@TWiStErRob 2016-08-03 20:50:20

@KonstantinosChalkias the built-in collections aren't thread safe either. Only the ones with the name Concurrent are really safe, the ones wrapped with Collections.synchronized() are semi-safe. Also the OP didn't say anything about concurrency so this is a valid, and good answer.

@muued 2016-08-12 14:17:28

The iterator returned here should not be able to remove elements from dta (this can be achieved via guava's Iterators.unmodifiableIterator for example). Otherwise the default implementations of e.g. removeAll and retainAll in AbstractSet and its parents working with that iterator will mess up your RandomSet!

@Gene 2016-09-02 13:33:26

Nice solution. You actually can use a tree if each node contains the number of nodes in the subtree it roots. Then compute a random real in 0..1 and make a weighted 3-way decision (select current node or descend into left or right subtree) at each node based on the node counts. But imo your solution is much nicer.

@Dustin Getz 2011-03-02 02:06:33

after reading this thread, the best i could write is:

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

@dimo414 2016-04-28 15:07:02

The question is asking about sets, not arrays. Also there's no need to seed Random with the current time; new Random() returns a properly-seeded instance out of the box.

@Dan Dyer 2008-09-24 19:38:30

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.

@mdma 2010-07-20 13:51:02

Copying to a list will cost O(n) in time and also use O(n) memory, so why would that be a better choice than fetching from the map directly?

@Dan Dyer 2011-04-12 00:10:04

It depends on how many times you want to pick from the set. The copy is a one time operation and then you can pick from the set as many times as you need. If you're only picking one element, then yes the copy doesn't make things any faster.

@TurnipEntropy 2017-04-15 13:58:35

It's only a one time operation if you want to be able to pick with repetition. If you want the chosen item to be removed from the set, then you would be back to O(n).

@Aaron McDaid 2010-07-20 13:45:31

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;
  u.max_load_factor(40);
  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;
  }
}

@pjb3 2008-12-23 03:51:32

Clojure solution:

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

@Bruno Kim 2013-03-24 07:19:35

This solution is also linear, because to get the nth element you must traverse the seq as well.

@Krzysztof Wolny 2016-09-02 20:37:52

It's linear also as it fits nicely in one line :D

@inglesp 2008-09-24 04:28:29

In lisp

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

@Ken 2010-12-20 03:41:53

This only works for lists, right? With ELT it could work for any sequence.

@Mathew Byrne 2008-09-24 00:35:18

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();

@marcospereira 2008-09-24 12:41:38

I prefer the second alternative. :-)

@matt lohkamp 2008-09-27 22:06:13

ooh, I like extending adding the new array method!

@Mitch Wheat 2008-09-24 03:32:31

In C#

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

        OrderedDictionary od = new OrderedDictionary();

        od.Add("abc", 1);
        od.Add("def", 2);
        od.Add("ghi", 3);
        od.Add("jkl", 4);


        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"]);

@Mitch Wheat 2011-06-17 00:32:16

Would the downvoter please leave a comment. Thanks.

@Federico Berasategui 2012-12-18 21:13:09

looks like they downvoted because the crappy java dictionary (or so called LinkedHashSet, whatever the hell that is) cannot be "randomly accessed" (which is being accessed by key, i guess). The java crap makes me laugh so much

@Hugh Allen 2008-09-24 01:46:43

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()

@J.J. 2008-09-24 00:51:41

Perl 5

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

Here is one way to do it.

@da5id 2008-09-24 00:28:40

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];

Related Questions

Sponsored Content

40 Answered Questions

[SOLVED] How to generate a random alpha-numeric string?

32 Answered Questions

[SOLVED] Generating random whole numbers in JavaScript in a specific range?

32 Answered Questions

[SOLVED] How do I generate a random int number?

  • 2010-04-24 23:09:11
  • Rella
  • 2140437 View
  • 1782 Score
  • 32 Answer
  • Tags:   c# random

20 Answered Questions

[SOLVED] Generate random number between two numbers in JavaScript

  • 2011-02-10 16:41:22
  • Mirgorod
  • 1312838 View
  • 1628 Score
  • 20 Answer
  • Tags:   javascript random

65 Answered Questions

[SOLVED] How do I generate random integers within a specific range in Java?

  • 2008-12-12 18:20:57
  • user42155
  • 3902798 View
  • 3361 Score
  • 65 Answer
  • Tags:   java random integer

36 Answered Questions

[SOLVED] How to pair socks from a pile efficiently?

21 Answered Questions

[SOLVED] What is reflection and why is it useful?

15 Answered Questions

[SOLVED] Why does this code using random strings print "hello world"?

  • 2013-03-03 04:38:06
  • 0x56794E
  • 194132 View
  • 1730 Score
  • 15 Answer
  • Tags:   java string random

65 Answered Questions

[SOLVED] Generate random string/characters in JavaScript

  • 2009-08-28 21:14:41
  • Tom Lehman
  • 1211175 View
  • 1581 Score
  • 65 Answer
  • Tags:   javascript random

13 Answered Questions

[SOLVED] Generating random numbers in Objective-C

  • 2008-10-02 04:35:21
  • rustyshelf
  • 444030 View
  • 735 Score
  • 13 Answer
  • Tags:   objective-c random

Sponsored Content