如何从集合中选择随机元素？
我特别有兴趣从
Java中的HashSet或者LinkedHashSet。
也欢迎使用其他语言的解决方案。

解决方案

由于我们说过"也欢迎使用其他语言的解决方案"，因此以下是适用于Python的版本：

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

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

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

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

在伪代码中-

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

PHP，假设" set"是一个数组：

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

Mersenne Twister功能更好，但在PHP中没有MT等效于array_rand。

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

Javascript解决方案;)

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

我们是否知道一些相关的信息：

java.util.Collections中有一些有用的方法可以对整个集合进行混洗：Collections.shuffle(List <？>)和Collections.shuffle(List <？list，随机rnd)。

Perl 5

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

这是一种方法。

Icon具有集合类型和一个随机元素运算符，一元"？"，因此表达式

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

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

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

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

口齿不清

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

如果要使用Java进行操作，则应考虑将元素复制到某种随机访问集合中(例如ArrayList)。因为，除非集合很小，否则访问所选元素将很昂贵(O(n)而不是O(1))。 [ed：列表副本也为O(n)]

或者，我们可以寻找另一个更符合需求的Set实现。 Commons Collections中的ListOrderedSet看起来很有希望。

Clojure解决方案：

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

不幸的是，这在任何标准库集合容器中都无法高效地完成(优于O(n))。

这很奇怪，因为向哈希集和二进制集添加随机选取函数非常容易。在不稀疏的哈希集中，我们可以尝试随机输入，直到获得成功为止。对于二叉树，我们可以在左子树或者右子树之间随机选择，最大步数为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]作为输出，因此分配接缝良好。

我为自己遇到了同样的问题，但我还没有决定使用这种基于python的集合所带来的开销值得这个更高效的选择的性能提升。我当然可以对其进行优化，然后将其转换为C，但是对于我来说，今天的工作太多了：)

C ++。这应该相当快，因为​​它不需要遍历整个集合或者对其进行排序。在大多数现代编译器都支持tr1的情况下，这应该可以立即使用。如果没有，我们可能需要使用Boost。

即使我们不使用Boost，Boost文档也会在这里进行解释。

诀窍是利用数据已被划分为存储桶的事实，并快速识别随机选择的存储桶(具有适当的概率)。

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