从一个集合中挑选一个随机元素

我如何从一组中随机select一个元素？ 我特别感兴趣的是从Java中的HashSet或LinkedHashSet中select一个随机元素。 其他语言的解决scheme也是受欢迎的。

Answer 1

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

Answer 2

有点相关你知道吗：

java.util.Collections用于混洗整个集合的有用方法： Collections.shuffle(List<?>)和Collections.shuffle(List<?> list, Random rnd) 。

Answer 3

Java使用ArrayList和HashMap快速解决scheme：[element – > index]。

动机：我需要一组具有RandomAccess属性的项目，尤其是从集合中选取一个随机项目（请参阅pollRandom方法）。 二叉树中的随机导航并不准确：树不是完全平衡的，不会导致均匀分布。

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

Answer 4

如果你想用Java来做，你应该考虑将元素复制到某种随机访问集合（如ArrayList）中。 因为，除非你的设置很小，访问选定的元素将是昂贵的（O（n）而不是O（1））。 [编辑：列表副本也O（n）]

或者，您可以查找更符合您的要求的另一个Set实现。 Commons Collections的ListOrderedSet看上去很有希望。

Answer 5

这比接受的答案中的for-each循环更快：

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

for-each构造在每一个循环上都调用Iterator.hasNext() ，但是自从index < set.size() ，这个检查是不必要的开销。 我看到速度提高了10-20％，但是YMMV。 （另外，这个编译不需要添加额外的return语句。）

请注意，此代码（以及大多数其他答案）可以应用于任何Collection，而不仅仅是Set。 通用方法forms：

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

Answer 6

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

Answer 7

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

Answer 8

Clojure解决scheme：

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

Answer 9

你不能只是获得集合/数组的大小/长度，生成一个介于0和大小/长度之间的随机数，然后调用索引匹配该数字的元素？ HashSet有一个.size（）方法，我很确定。

在psuedocode中 –

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

Answer 10

Perl 5

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

这是一个办法。

Answer 11

C ++。 这应该是相当快的，因为它不需要遍历整个集合，也不需要对它进行sorting。 这应该与现代编译器一起使用，假设它们支持tr1 。 如果没有，您可能需要使用Boost。

即使您不使用Boost， Boost文档也可以帮助您解释这一点。

诀窍是利用数据被分成桶的事实，并快速识别随机select的桶（以适当的概率）。

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

Answer 12

上面的解决scheme在延迟方面说话，但并不保证每个索引被select的概率相等。
如果需要考虑，请尝试油藏采样。 http://en.wikipedia.org/wiki/Reservoir_sampling 。
Collections.shuffle（）（如less数人所build议的）使用一种这样的algorithm。

Answer 13

PHP，假设“set”是一个数组：

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

Mersenne Twister函数更好，但是在PHP中没有MT的array_rand。

Answer 14

图标有一个集合types和一个随机元素运算符，一元“？”，所以expression式

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

会产生一个1到5之间的随机数。

随机种子在程序运行时被初始化为0，所以在每次运行时产生不同的结果，使用randomize()

Answer 15

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

Answer 16

Javascript解决scheme;）

 function choose (set) { return set[Math.floor(Math.random() * set.length)]; } var set = [1, 2, 3, 4], rand = choose (set); 

或者：

 Array.prototype.choose = function () { return this[Math.floor(Math.random() * this.length)]; }; [1, 2, 3, 4].choose(); 

Answer 17

在lisp

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

Answer 18

在Mathematica中：

 a = {1, 2, 3, 4, 5} a[[ ⌈ Length[a] Random[] ⌉ ]] 

或者在最近的版本中，简单地说：

 RandomChoice[a] 

---

由于缺乏解释，所以得到了低票，所以这里是：

Random[]生成一个0到1之间的伪随机数。这个值乘以列表的长度，然后使用ceiling函数四舍五入到下一个整数。 这个索引然后从a提取。

由于散列表function经常在Mathematica中使用规则完成，并且规则存储在列表中，所以可以使用：

 a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4}; 

Answer 19

那么刚刚

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

Answer 20

这与接受的答案（Khoth）是一样的，但是不必要的size和ivariables被删除。

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

尽pipe放弃了前面提到的两个variables，但是上面的解决scheme仍然是随机的，因为我们依赖随机（从随机select的索引处开始）在每次迭代中将其自身递减到0 。

Answer 21

不幸的是，在任何标准库集合容器中都不能有效地完成（比O（n）好）。

这很奇怪，因为向散列集合和二进制集合添加随机选取函数是非常容易的。 在一个不稀疏的哈希集，你可以尝试随机的条目，直到你得到一个命中。 对于二叉树，您可以在左侧或右侧的子树之间随机select，最多为O（log2）个步骤。 我已经实现了以下的演示：

 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 

我得到了[995,975,971,995,1057,1004,966,1052,984,1001]作为输出，所以分配接缝良好。

我为自己的同样的问题挣扎，我还没有决定天气，这个更有效的select的性能增益值得使用基于Python的集合的开销。 我当然可以改进它，并将其转化为C，但对我来说这太多了:)

Answer 22

既然你说过“其他语言的解决scheme也是受欢迎的”，下面是Python的版本：

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

Answer 23

PHP，使用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]; 

Answer 24

为了好玩，我写了一个基于拒绝采样的RandomHashSet。 这有点不好意思，因为HashMap不允许我们直接访问它的表，但它应该工作得很好。

它不使用任何额外的内存，查找时间是O（1）摊销。 （因为Java HashTable是密集的）。

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

Answer 25

你也可以将设置转移到数组使用数组，它可能会在小范围内工作，我看到在最投票答案的循环是O（N）反正

 Object[] arr = set.toArray(); int v = (int) arr[rnd.nextInt(arr.length)]; 

Answer 26

如果你真的只想从Setselect“任何”对象，而没有对随机性的任何保证，那么最简单的方法是把迭代器返回的第一个对象。

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

Answer 27

Java 8最简单的是：

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

其中n是一个随机整数。 当然它的performance要比那些for(elem: Col)

Answer 28

以Khoth的答案为出发点的通用解决scheme。

 /** * @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; } 

Answer 29

如果设置的大小不是很大，那么通过使用数组可以完成。

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

Answer 30

用番石榴，我们可以比Khoth的答案做得更好一点：

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