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

小开

既然你说“其他语言的解决方案也欢迎”，下面是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中没有与array_rand等效的MT函数。

小开

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, Random rnd)。

小开

Perl 5

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

这里有一种方法。

小开

图标有一个set类型和一个随机元素操作符，一元的"?"，所以表达式

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

小开

在lisp中

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

小开

如果您希望在Java中执行此操作，则应该考虑将元素复制到某种随机访问集合(例如ArrayList)中。因为，除非你的集合很小，否则访问所选元素的代价会很高(O(n)而不是O(1))。[ed: list copy也是O(n)]

或者，您可以寻找另一个更符合您需求的Set实现。公共集合中的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。

诀窍在于利用数据已被划分为多个bucket的事实，并快速识别随机选择的bucket(具有适当的概率)。

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

小开

读完这篇文章后，我能写的最好的是:

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

小开

使用ArrayList和HashMap: [element ->索引]的Java快速解决方案。

动机:我需要一组具有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();
}
}

小开

数学:

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


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

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

RandomChoice[a]

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

由于哈希表功能在Mathematica中经常使用规则，并且规则存储在列表中，因此可以使用:

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

小开

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

它不使用任何额外的内存，查找时间是O(1)平摊。(因为java哈希表是密集的)。

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

小开

这比接受答案中的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语句。)

请注意，这段代码(以及大多数其他答案)可以应用于任何集合，而不仅仅是集合。通用方法形式:

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

小开

你也可以使用array将set转换为数组它可能会在小范围内工作，我看到for循环中投票最多的答案是O(n)无论如何

Object[] arr = set.toArray();


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

小开

这与接受的答案(Khoth)相同，但删除了不必要的size和i变量。

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

虽然去掉了前面提到的两个变量，但上面的解决方案仍然是随机的，因为我们依赖于random(从随机选择的索引开始)在每次迭代中自减到0。

小开

上面的解决方案是从延迟的角度讲的，但不能保证每个索引被选择的概率相等如果需要考虑这一点，可以尝试储层取样。http://en.wikipedia.org/wiki/Reservoir_sampling。
Collections.shuffle()(正如少数人建议的那样)使用这样的算法

小开

如果你真的只想从Set中选择“任意”对象，而不保证随机性，最简单的方法是获取迭代器返回的第一个对象。

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

小开

Java 8最简单的方法是:

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

其中n是一个随机整数。当然，它的性能不如for(elem: Col)

小开

以霍斯的答案为起点的通用解决方案。

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

小开

如果设置的大小不是很大，那么使用数组可以做到这一点。

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

小开

使用番石榴，我们可以做得比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);
}

小开

如果你不介意第三方库，跑龙套库有一个IterableUtils，它有一个randomFrom(Iterable Iterable)方法，该方法将接受一个Set并从中返回一个随机元素

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

它在Maven中央存储库中:

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

小开

在Java 8中:

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

小开

Java 8+流:

    static <E> Optional<E> getRandomElement(Collection<E> collection) {
return collection
.stream()
.skip(ThreadLocalRandom.current()
.nextInt(collection.size()))
.findAny();
}

基于约书亚骨的回答，但略有变化:

忽略Streams元素的顺序，以便在并行操作中略微提高性能
使用当前线程的ThreadLocalRandom
接受任何集合类型作为输入
返回提供的Optional而不是null